953. Verifying an Alien Dictionary

EasyArrayHash TableString

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You're given words from an alien language that uses the same 26 lowercase English letters (a-z), but in a potentially different alphabetical order. The aliens have their own custom ordering of these letters.

Your task is to determine whether a given list of words is sorted according to the alien dictionary order.

Input:

words: A list of strings containing words written in the alien language
order: A string of 26 characters representing the alien alphabetical order (a permutation of a-z)

Output:

Return true if the words are sorted lexicographically according to the alien order
Return false otherwise

Example: If the alien order is "hlabcdefgijkmnopqrstuvwxyz" (where h comes before l, which comes before a, etc.), then:

["hello", "leetcode"] would be sorted correctly because h comes before l in the alien order
["word", "world"] would need to be checked character by character using the alien order

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Map each alien letter to its rank, then verify each adjacent word pair is in order under that mapping.

Open in Flowchart

Intuition

To check if words are sorted in an alien dictionary, we need to compare them the same way we'd compare words in a regular dictionary - character by character from left to right. The key insight is that we need to translate the alien ordering into something we can work with numerically.

Think about how you check if words are sorted in English: you compare the first letters, and if they're the same, you move to the second letters, and so on. The difference here is that instead of using the standard a < b < c... ordering, we have a custom ordering defined by the order string.

The natural approach is to create a mapping where each character gets assigned its position in the alien alphabet. For example, if order = "bac...", then b has position 0, a has position 1, and c has position 2. This way, we can compare characters numerically - a character with a smaller position value comes before one with a larger position value.

A list is sorted exactly when every adjacent pair of words is sorted, because lexicographic order is transitive. So the solution compares words[i - 1] with words[i] for each i. For one pair, it scans both words from the left until the first position where the characters differ. That first difference decides the order: if the earlier word's character has a larger position value, the list is not sorted; if it has a smaller one, this pair is fine and the rest of the characters do not matter.

Words of different lengths need one extra rule. If no difference is found within the shorter length, one word is a prefix of the other. The shorter word must come first, so "app" before "apple" is fine, but "apple" before "app" is not sorted.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution compares each pair of adjacent words using the alien alphabet:

Step 1: Create Character-to-Position Mapping

char_to_position = {char: position for position, char in enumerate(order)}

This creates a dictionary where each character maps to its position in the alien alphabet. For example, if order = "bac...", then char_to_position = {'b': 0, 'a': 1, 'c': 2, ...}.

Step 2: Iterate Over Adjacent Pairs

for i in range(1, len(words)):
    previous_word = words[i - 1]
    current_word = words[i]

If every adjacent pair is in order, the whole list is in order, so it is enough to check n - 1 pairs.

Step 3: Find the First Differing Character

for j in range(min_length):
    previous_value = char_to_position[previous_word[j]]
    current_value = char_to_position[current_word[j]]
    if previous_value > current_value:
        return False
    if previous_value < current_value:
        found_difference = True
        break

The loop only runs over min_length = min(len(previous_word), len(current_word)) positions, so it never reads past the end of either word.

If previous_value > current_value, the earlier word's character comes later in the alien alphabet, so the list is not sorted.
If previous_value < current_value, this position decides the pair in the correct order. The loop stops, since later characters cannot change the result.
If the values are equal, the loop moves to the next position.

Step 4: Handle the Prefix Case

if not found_difference and len(previous_word) > len(current_word):
    return False

If no difference was found, the shorter word is a prefix of the longer one. The shorter word must come first. For example, ["apple", "app"] is not sorted, while ["app", "apple"] is.

Step 5: Return True If every adjacent pair passes, the words are sorted.

Example Walkthrough

Let's walk through the algorithm with a concrete example:

Input:

words = ["cat", "car", "card"]
order = "cabdefghijklmnopqrstuvwxyz" (where 'c' comes first, then 'a', then 'b', etc.)

Step 1: Create mapping

char_to_position = {'c': 0, 'a': 1, 'b': 2, 'd': 3, ..., 'r': 17, ..., 't': 19, ...}

Step 2: Compare the pair "cat" and "car" (i = 1)

min_length = min(3, 3) = 3
j = 0: 'c' → 0, 'c' → 0. Equal, continue.
j = 1: 'a' → 1, 'a' → 1. Equal, continue.
j = 2: 't' → 19, 'r' → 17. Since 19 > 17, return False.

Result: Return False

The words are not sorted according to the alien dictionary because 't' comes after 'r' in the alien alphabet, so "cat" should come after "car". The pair "car" and "card" is never checked.

For comparison, with words = ["car", "card", "cat"] and the same order:

"car" vs "card": positions 0 to 2 are all equal, so found_difference stays False. The earlier word is shorter (3 < 4), so the pair is fine.
"card" vs "cat": j = 2 compares 'r' → 17 with 't' → 19. Since 17 < 19, the pair is fine.
All pairs pass, so the result is True.

Solution Implementation

1class Solution:
2    def isAlienSorted(self, words: List[str], order: str) -> bool:
3        # Create a mapping from each character to its position in the alien alphabet
4        char_to_position = {char: position for position, char in enumerate(order)}
5
6        # Compare each adjacent pair of words
7        for i in range(1, len(words)):
8            previous_word = words[i - 1]
9            current_word = words[i]
10            min_length = min(len(previous_word), len(current_word))
11            found_difference = False
12
13            # Compare characters at each position up to the shorter length
14            for j in range(min_length):
15                previous_value = char_to_position[previous_word[j]]
16                current_value = char_to_position[current_word[j]]
17
18                # Previous word's character comes later in the alien order: not sorted
19                if previous_value > current_value:
20                    return False
21
22                # The first differing character decides the order of this pair
23                if previous_value < current_value:
24                    found_difference = True
25                    break
26
27            # All compared characters are equal, but the previous word is longer
28            # Example: "apple" must not come before "app"
29            if not found_difference and len(previous_word) > len(current_word):
30                return False
31
32        # Every adjacent pair is in order
33        return True
34

1class Solution {
2    public boolean isAlienSorted(String[] words, String order) {
3        // Map each character to its position in the alien alphabet
4        int[] orderMap = new int[26];
5        for (int i = 0; i < 26; i++) {
6            orderMap[order.charAt(i) - 'a'] = i;
7        }
8
9        // Compare each adjacent pair of words
10        for (int i = 1; i < words.length; i++) {
11            String previousWord = words[i - 1];
12            String currentWord = words[i];
13            int minLength = Math.min(previousWord.length(), currentWord.length());
14            boolean foundDifference = false;
15
16            // Compare characters at each position up to the shorter length
17            for (int j = 0; j < minLength; j++) {
18                int previousValue = orderMap[previousWord.charAt(j) - 'a'];
19                int currentValue = orderMap[currentWord.charAt(j) - 'a'];
20
21                // Previous word's character comes later in the alien order: not sorted
22                if (previousValue > currentValue) {
23                    return false;
24                }
25
26                // The first differing character decides the order of this pair
27                if (previousValue < currentValue) {
28                    foundDifference = true;
29                    break;
30                }
31            }
32
33            // All compared characters are equal, but the previous word is longer
34            // Example: "apple" must not come before "app"
35            if (!foundDifference && previousWord.length() > currentWord.length()) {
36                return false;
37            }
38        }
39
40        // Every adjacent pair is in order
41        return true;
42    }
43}
44

1class Solution {
2public:
3    bool isAlienSorted(vector<string>& words, string order) {
4        // Map each character to its position in the alien alphabet
5        vector<int> charToPosition(26);
6        for (int i = 0; i < 26; ++i) {
7            charToPosition[order[i] - 'a'] = i;
8        }
9
10        // Compare each adjacent pair of words
11        for (int i = 1; i < words.size(); ++i) {
12            const string& previousWord = words[i - 1];
13            const string& currentWord = words[i];
14            int minLength = min(previousWord.size(), currentWord.size());
15            bool foundDifference = false;
16
17            // Compare characters at each position up to the shorter length
18            for (int j = 0; j < minLength; ++j) {
19                int previousValue = charToPosition[previousWord[j] - 'a'];
20                int currentValue = charToPosition[currentWord[j] - 'a'];
21
22                // Previous word's character comes later in the alien order: not sorted
23                if (previousValue > currentValue) {
24                    return false;
25                }
26
27                // The first differing character decides the order of this pair
28                if (previousValue < currentValue) {
29                    foundDifference = true;
30                    break;
31                }
32            }
33
34            // All compared characters are equal, but the previous word is longer
35            // Example: "apple" must not come before "app"
36            if (!foundDifference && previousWord.size() > currentWord.size()) {
37                return false;
38            }
39        }
40
41        // Every adjacent pair is in order
42        return true;
43    }
44};
45

1/**
2 * Verifies if words are sorted according to an alien dictionary order
3 * @param words - Array of words to check if they are in lexicographical order
4 * @param order - String representing the alien alphabet order
5 * @returns true if words are sorted according to the alien order, false otherwise
6 */
7function isAlienSorted(words: string[], order: string): boolean {
8    // Create a map to store character positions in the alien alphabet
9    const charToOrderMap = new Map<string, number>();
10  
11    // Map each character to its position in the alien alphabet
12    for (const char of order) {
13        charToOrderMap.set(char, charToOrderMap.size);
14    }
15  
16    const wordCount = words.length;
17  
18    // Compare each adjacent pair of words
19    for (let i = 1; i < wordCount; i++) {
20        const previousWord = words[i - 1];
21        const currentWord = words[i];
22        const minLength = Math.min(previousWord.length, currentWord.length);
23        let foundDifference = false;
24      
25        // Compare characters at each position
26        for (let j = 0; j < minLength; j++) {
27            const previousCharOrder = charToOrderMap.get(previousWord[j])!;
28            const currentCharOrder = charToOrderMap.get(currentWord[j])!;
29          
30            // If previous word's character comes after current word's character, not sorted
31            if (previousCharOrder > currentCharOrder) {
32                return false;
33            }
34          
35            // If we found a character that determines the order, mark and break
36            if (previousCharOrder < currentCharOrder) {
37                foundDifference = true;
38                break;
39            }
40        }
41      
42        // If all compared characters are equal but previous word is longer, not sorted
43        // Example: "apple" should not come before "app"
44        if (!foundDifference && previousWord.length > currentWord.length) {
45            return false;
46        }
47    }
48  
49    return true;
50}
51

Time and Space Complexity

Time Complexity: O(C) where C is the total number of characters across all words.

Creating the mapping takes O(26) = O(1) time.
Each adjacent pair (words[i - 1], words[i]) is compared for at most min(len(words[i - 1]), len(words[i])) positions, which is at most len(words[i - 1]).
Summing over all pairs, the total number of character comparisons is at most the total length of all words, C.

Space Complexity: O(1)

The mapping stores 26 entries, which is constant.
The loop variables (previous_word, current_word, min_length, found_difference, previous_value, current_value) are references or integers and take O(1) space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Mishandling the Prefix Case

When one word is a prefix of the other, no character pair differs, so a loop that only looks for differing characters ends without deciding anything. Returning True at that point is wrong when the longer word comes first.

Problem Example:

Alien order: "abcdefghijklmnopqrstuvwxyz" (standard order)
Words: ["apple", "app"]
Expected: False, because "app" must come before "apple"

Incorrect:

for j in range(min_length):
    if previous_value > current_value:
        return False
    if previous_value < current_value:
        break
# Missing check: falls through and treats ["apple", "app"] as sorted

Solution: After the loop, if no difference was found and len(previous_word) > len(current_word), return False.

2. Checking Columns Across All Words Instead of Adjacent Pairs

Another tempting approach scans column by column: for position 0, check that the first letters of all words are non-decreasing; then do the same for position 1, and so on. This is wrong because a later column only matters for pairs that were tied in all earlier columns.

Incorrect:

for col in range(20):
    prev = -1
    for word in words:
        curr = -1 if col >= len(word) else char_to_position[word[col]]
        if prev > curr:
            return False
        prev = curr

Problem Example: With the standard order, words = ["ab", "ac", "ba"] is sorted. Column 0 is a, a, b (fine), but column 1 is b, c, a, and the check c > a returns False, even though "ac" and "ba" were already ordered by column 0.

Solution: Compare adjacent words pairwise and stop at the first differing character of each pair, as the shown solution does.

3. Comparing Characters by Their English Order

Using previous_word[j] > current_word[j] compares characters by their standard ASCII order, not the alien order.

Problem Example: With order = "hlabcdefgijkmnopqrstuvwxyz", words = ["hello", "leetcode"] is sorted because h comes before l in the alien order. A plain character comparison happens to agree here, but for words = ["la", "ab"] it reports 'l' > 'a' (not sorted), while in the alien order l comes before a, so the list is sorted.

Solution: Always compare char_to_position[...] values, never the characters themselves.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know