Skip to content

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<string>& words, const string& order) {
    vector<char> map(26);  // e.g. 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(words.begin(), words.end());
  }
};

 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]; // e.g. 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:]))