# 953. Verifying an Alien Dictionary

• Time: $O(n)$
• Space: $O(26) = O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public: bool isAlienSorted(vector& words, const string& order) { vector map(26); // order = "bca" -> map = ['c', 'a', 'b'] for (int i = 0; i < 26; ++i) map[order[i] - 'a'] = i + 'a'; for (string& word : words) for (char& c : word) c = map[c - 'a']; return is_sorted(begin(words), end(words)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean isAlienSorted(String[] words, String order) { char[] map = new char[26]; // order = "bca" -> map = ['c', 'a', 'b'] for (int i = 0; i < 26; ++i) map[order.charAt(i) - 'a'] = (char) (i + 'a'); for (int i = 0; i + 1 < words.length; ++i) if (bigger(words[i], words[i + 1], map)) return false; return true; } private boolean bigger(final String s1, final String s2, final char[] map) { for (int i = 0; i < s1.length() && i < s2.length(); ++i) if (s1.charAt(i) != s2.charAt(i)) return map[s1.charAt(i) - 'a'] > map[s2.charAt(i) - 'a']; return s1.length() > s2.length(); } } 
 1 2 3 4 5 class Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: dict = {c: i for i, c in enumerate(order)} words = [[dict[c] for c in word] for word in words] return all(w1 <= w2 for w1, w2 in zip(words, words[1:]))