Verifying an Alien Dictionary

Difficulty: Easy Source: NeetCode

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 English letters.

Given a list 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.

Example 1: Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true

Example 2: Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false

Example 3: Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• All characters in words[i] and order are English lowercase letters

Prerequisites

Before attempting this problem, you should be comfortable with:

• Hash Maps — mapping characters to their rank for O(1) lookup
• String comparison — comparing two strings character by character

1. Brute Force

Intuition

Compare every adjacent pair of words. For each pair, go character by character: if the characters are the same, keep going; if they differ, the pair is ordered correctly only if the first word’s character comes before the second’s in the alien order; if one word is a prefix of the other, the shorter one must come first. If any adjacent pair is out of order, return False.

Algorithm

1. Build a rank map: rank[order[i]] = i for each index i.
2. For each adjacent pair (words[i], words[i+1]):
   • Compare character by character up to the shorter length.
   • If chars differ: check rank[c1] < rank[c2]; if not, return False.
   • If one is a prefix of the other: words[i] must not be longer than words[i+1].
3. Return True if all pairs pass.

Solution

def isAlienSorted(words: list[str], order: str) -> bool:
    rank = {ch: i for i, ch in enumerate(order)}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        for j in range(len(w1)):
            if j == len(w2):
                # w2 is a prefix of w1 → wrong order
                return False
            if w1[j] != w2[j]:
                if rank[w1[j]] > rank[w2[j]]:
                    return False
                break  # this pair is correctly ordered; move on

    return True


print(isAlienSorted(["hello","leetcode"], "hlabcdefgijkmnopqrstuvwxyz"))  # True
print(isAlienSorted(["word","world","row"], "worldabcefghijkmnpqstuvxyz"))  # False
print(isAlienSorted(["apple","app"], "abcdefghijklmnopqrstuvwxyz"))         # False

Complexity

• Time: O(N * L) where N = number of words, L = average word length
• Space: O(1) — the rank map is always exactly 26 entries

2. Sorted Key Comparison

Intuition

Python’s sorted() with a custom key can do this elegantly. Map each word to a tuple of alien ranks, then check if words already equals the sorted version. This is more Pythonic but has the same asymptotic complexity.

Algorithm

1. Build rank map as before.
2. Define alien_key(word) = tuple of rank[ch] for each char in word.
3. Return words == sorted(words, key=alien_key).

Solution

def isAlienSorted(words: list[str], order: str) -> bool:
    rank = {ch: i for i, ch in enumerate(order)}

    def alien_key(word):
        return [rank[ch] for ch in word]

    return words == sorted(words, key=alien_key)


print(isAlienSorted(["hello","leetcode"], "hlabcdefgijkmnopqrstuvwxyz"))  # True
print(isAlienSorted(["word","world","row"], "worldabcefghijkmnpqstuvxyz"))  # False
print(isAlienSorted(["apple","app"], "abcdefghijklmnopqrstuvwxyz"))         # False
print(isAlienSorted(["z","x"], "zyxwvutsrqponmlkjihgfedcba"))              # True

Complexity

• Time: O(N * L * log N) due to sorting
• Space: O(N * L) for the key tuples

Common Pitfalls

Prefix case: longer word first. If words[i] is a prefix of words[i+1] (e.g., “apple” before “app”), the words are out of order. Check j == len(w2) inside the character loop — if you exhaust w2 before finding a difference, that’s wrong order.

Breaking after the first differing character. Once you find the first character that differs between two words, that single comparison decides the pair’s order. Don’t continue comparing further characters — break after the if rank[w1[j]] > rank[w2[j]]: return False check.

Building the rank map correctly. rank = {ch: i for i, ch in enumerate(order)} — make sure the index is the rank (position in the alien alphabet), not the character value.