LeetCode 953: Verifying an Alien Dictionary

Problem Restatement

We are given:

1. A list of words called words
2. A string called order

The string order describes the alphabet order used in an alien language.

We need to check whether the words are sorted lexicographically according to this alien alphabet.

Return true if the list is correctly sorted. Otherwise, return false.

The official constraints are:

Source: LeetCode problem statement. (leetcode.com)

Input and Output

Example function shape:

def isAlienSorted(words: list[str], order: str) -> bool:
    ...

Examples

Example 1:

words = ["hello", "leetcode"]
order = "hlabcdefgijkmnopqrstuvwxyz"

Output:

True

Explanation:

The alien alphabet starts with:

h < l < a < b < ...

Compare:

"hello"
"leetcode"

The first different characters are:

h and l

Since h < l in the alien order, the words are correctly sorted.

Example 2:

words = ["word", "world", "row"]
order = "worldabcefghijkmnpqstuvxyz"

Output:

False

Explanation:

Compare:

"word"
"world"

The first different characters are:

d and l

In the alien order:

l comes before d

So "word" should appear after "world".

Example 3:

words = ["apple", "app"]
order = "abcdefghijklmnopqrstuvwxyz"

Output:

False

Explanation:

The shorter word should come first when one word is a prefix of the other.

So:

"app" < "apple"

But the list gives the reverse order.

First Thought: Use Normal String Comparison

Python already supports string comparison:

"abc" < "abd"

But Python uses the normal English alphabet order.

This problem uses a custom alphabet.

So we cannot compare characters directly.

Instead, we must map each character to its alien position.

Key Insight

Lexicographical comparison works like dictionary comparison.

We compare two words character by character.

At the first position where they differ:

• the smaller character decides the smaller word
• later characters no longer matter

Example:

abc
abd

The first difference is:

c vs d

Since c < d, the first word is smaller.

We can simulate this by assigning each alien character a rank.

Example:

order = "hlabcdefgijkmnopqrstuvwxyz"

Then:

rank['h'] = 0
rank['l'] = 1
rank['a'] = 2
...

Now we can compare characters using numeric ranks.

Algorithm

Create a dictionary:

character -> alien rank

Then compare every adjacent pair of words.

For each pair:

1. Compare characters from left to right.
2. Stop at the first different character.
3. If the first word has a larger alien rank, return False.
4. If the first word has a smaller alien rank, the pair is valid.
5. If all compared characters are equal, the shorter word must come first.

If all adjacent pairs are valid, return True.

Prefix Rule

This is the most important edge case.

Consider:

"apple"
"app"

All compared characters match:

a == a
p == p
p == p

Now one word ends.

In lexicographical ordering, the shorter word is smaller.

So:

"app" < "apple"

Therefore:

["apple", "app"]

is invalid.

Correctness

We compare each adjacent pair of words because a list is sorted if and only if every adjacent pair is sorted.

For a pair of words, lexicographical order depends on the first position where the characters differ.

If at that position the first word has a character with larger alien rank, then the first word should appear later, so the ordering is invalid.

If the first word has a smaller alien rank, then the pair is correctly ordered, and later characters do not matter.

If all compared characters are equal, then one word is a prefix of the other. In lexicographical ordering, the shorter word must come first. Therefore, if the first word is longer than the second word while sharing the same prefix, the ordering is invalid.

The algorithm checks exactly these conditions for every adjacent pair. Therefore, it correctly determines whether the full list is sorted according to the alien alphabet.

Complexity

Let:

n = len(words)
m = average word length

The alphabet size is fixed, so the rank dictionary uses constant space.

Implementation

class Solution:
    def isAlienSorted(self, words: list[str], order: str) -> bool:
        rank = {
            char: index
            for index, char in enumerate(order)
        }

        for i in range(len(words) - 1):
            word1 = words[i]
            word2 = words[i + 1]

            min_length = min(len(word1), len(word2))

            found_difference = False

            for j in range(min_length):
                c1 = word1[j]
                c2 = word2[j]

                if c1 != c2:
                    if rank[c1] > rank[c2]:
                        return False

                    found_difference = True
                    break

            if not found_difference and len(word1) > len(word2):
                return False

        return True

Code Explanation

We first build the alien rank mapping:

rank = {
    char: index
    for index, char in enumerate(order)
}

Example:

order = "hlabcdefgijkmnopqrstuvwxyz"

creates:

rank['h'] = 0
rank['l'] = 1
rank['a'] = 2
...

Then we compare every adjacent pair:

for i in range(len(words) - 1):

We extract the two current words:

word1 = words[i]
word2 = words[i + 1]

We compare only up to the shorter length:

min_length = min(len(word1), len(word2))

Inside the loop:

if c1 != c2:

we found the first meaningful difference.

If the alien rank is reversed:

if rank[c1] > rank[c2]:
    return False

then the list is not sorted.

Otherwise, this pair is valid, so we stop checking this pair:

found_difference = True
break

After the loop, if no difference was found:

if not found_difference and len(word1) > len(word2):

then one word is a prefix of the other.

If the first word is longer, the ordering is invalid.

If all pairs pass, we return:

return True

Testing

def run_tests():
    s = Solution()

    assert s.isAlienSorted(
        ["hello", "leetcode"],
        "hlabcdefgijkmnopqrstuvwxyz"
    ) is True

    assert s.isAlienSorted(
        ["word", "world", "row"],
        "worldabcefghijkmnpqstuvxyz"
    ) is False

    assert s.isAlienSorted(
        ["apple", "app"],
        "abcdefghijklmnopqrstuvwxyz"
    ) is False

    assert s.isAlienSorted(
        ["app", "apple"],
        "abcdefghijklmnopqrstuvwxyz"
    ) is True

    assert s.isAlienSorted(
        ["z", "x"],
        "zyxwvutsrqponmlkjihgfedcba"
    ) is True

    assert s.isAlienSorted(
        ["kuvp", "q"],
        "ngxlkthsjuoqcpavbfdermiywz"
    ) is True

    print("all tests passed")

run_tests()

Test meaning: