Problem

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.

Examples

Example 1:

1
2
3
4
5

Input:
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output:
 true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

1
2
3
4
5

Input:
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output:
 false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

1
2
3
4
5

Input:
words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output:
 false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character ([More info](https://en.wikipedia.org/wiki/Lexicographical_order)).

Solution

Method 1 – Hash Map for Character Order

Intuition

The main idea is to map each character in the alien language to its position in the given order string. By comparing each pair of adjacent words, we can check if the first differing character in the two words respects the alien order. If all pairs are in order, the list is sorted.

Approach

  1. Build a hash map pos mapping each character in order to its index.
  2. For each adjacent pair of words, compare characters one by one:
    • If characters differ, check their order using pos.
    • If the first word is longer but all characters match, return false.
  3. If all pairs are valid, return true.

Complexity

  • ⏰ Time complexity: O(N * L), where N is the number of words and L is the average word length.
  • 🧺 Space complexity: O(1), since the hash map size is fixed (26 letters).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> pos(26);
        for (int i = 0; i < order.size(); ++i) pos[order[i] - 'a'] = i;
        for (int i = 0; i < words.size() - 1; ++i) {
            string& w1 = words[i], &w2 = words[i+1];
            int len = min(w1.size(), w2.size());
            bool diff = false;
            for (int j = 0; j < len; ++j) {
                if (w1[j] != w2[j]) {
                    if (pos[w1[j] - 'a'] > pos[w2[j] - 'a']) return false;
                    diff = true;
                    break;
                }
            }
            if (!diff && w1.size() > w2.size()) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] pos = new int[26];
        for (int i = 0; i < order.length(); i++) pos[order.charAt(i) - 'a'] = i;
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i+1];
            int len = Math.min(w1.length(), w2.length());
            boolean diff = false;
            for (int j = 0; j < len; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (pos[w1.charAt(j) - 'a'] > pos[w2.charAt(j) - 'a']) return false;
                    diff = true;
                    break;
                }
            }
            if (!diff && w1.length() > w2.length()) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def isAlienSorted(self, words: list[str], order: str) -> bool:
        pos = {c: i for i, c in enumerate(order)}
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i+1]
            for j in range(min(len(w1), len(w2))):
                if w1[j] != w2[j]:
                    if pos[w1[j]] > pos[w2[j]]:
                        return False
                    break
            else:
                if len(w1) > len(w2):
                    return False
        return True