Verifying an Alien Dictionary: Custom Sort Order Validation

LeetCode 953, Verifying an Alien Dictionary, is an easy problem that asks you to check whether a list of words is sorted according to a custom alphabet. The alien language uses the same 26 lowercase English letters, but in a different order. Your job is to determine whether the given words respect that order.

The problem

You are given a list of words and a string representing the alphabet order of an alien language. Return true if the words are sorted lexicographically according to that alien order, or false otherwise.

Input:  words = ["hello", "leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: True

In the alien language, 'h' comes before 'l' because 'h' appears at index 0 and 'l' at index 1 in the order string. Since "hello" starts with 'h' and "leetcode" starts with 'l', and 'h' precedes 'l' in the alien alphabet, the pair is correctly sorted.

Why this problem matters

Verifying an Alien Dictionary teaches you how to generalize lexicographic comparison. In standard string comparison, you rely on the built-in character ordering (a, b, c, ..., z). But many real-world problems involve custom orderings: priority lists, locale-specific sorting rules, or domain-specific rankings. The technique of mapping characters to indices and then comparing those indices is the foundation for all of them.

This problem also reinforces the pairwise comparison pattern. You do not need to sort the list yourself. You just need to verify that every adjacent pair is in the correct order. This is the same principle behind checking whether an array is already sorted: compare each element with the next one.

Finally, the problem is a clean exercise in hash map construction. Building a lookup table from a string and then querying it during comparisons is a pattern you will use in dozens of other problems, from anagram detection to custom sort orders.

The key insight

Instead of trying to compare characters directly using some complex alien alphabet logic, you can reduce this problem to something familiar. Build a hash map that maps each character in the alien order to its position index. Then, comparing two characters in the alien alphabet is just comparing two integers.

Walking through it step by step

Let us trace through words = ["hello", "leetcode"] with order = "hlabcdefgijkmnopqrstuvwxyz".

The comparison resolved on the very first character. In cases where the first characters match, you would continue to the second character, then the third, and so on, until you find a difference or one word ends. If one word is a prefix of the other, the shorter word must come first for the pair to be sorted.

The solution

def isAlienSorted(words, order):
    order_map = {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):
                return False
            if w1[j] != w2[j]:
                if order_map[w1[j]] > order_map[w2[j]]:
                    return False
                break
    return True

Here is what each piece does:

1. Build order_map by iterating over the alien order string and storing each character with its index. This gives you O(1) lookups for character positions.
2. Iterate over every adjacent pair of words (words[i], words[i + 1]).
3. For each pair, compare characters at the same position from left to right.
4. If you exhaust the characters of the second word before finding a difference (j >= len(w2)), the first word is longer and has the second word as a prefix. This means they are out of order, so return False.
5. When you find the first position where the characters differ, compare their alien order indices. If the first word's character has a higher index, the pair is out of order, so return False. Otherwise, break out of the inner loop because this pair is confirmed sorted.
6. If all pairs pass, return True.

Complexity analysis

The time complexity is O(n * m) because you compare each adjacent pair of words, and each comparison scans at most m characters. Building the order map takes O(26) which is O(1). The space is O(1) because the order map always contains exactly 26 entries regardless of input size.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Custom comparator via index mapping

The pattern of converting a custom ordering into a position lookup table so you can compare elements with simple integer comparisons:

order_map = {ch: i for i, ch in enumerate(custom_order)}
def comes_before(a, b):
    return order_map[a] < order_map[b]

In Verifying an Alien Dictionary, the custom order is the alien alphabet. In Custom Sort String, the custom order defines a priority for characters. In problems involving rank-based comparisons, the same idea applies: map each element to its rank, then compare ranks.

2. Pairwise adjacent comparison

The pattern of verifying a sequence property by checking every consecutive pair:

for i in range(len(sequence) - 1):
    if not valid_pair(sequence[i], sequence[i + 1]):
        return False
return True

In Verifying an Alien Dictionary, you check that each word comes before the next in alien order. In "check if array is sorted" problems, you check that each element is not greater than the next. In linked list cycle detection, you check adjacent node relationships. The skeleton is always the same: iterate over consecutive pairs and verify a condition.

Edge cases

Before submitting, make sure your solution handles these:

• All identical words ["abc", "abc", "abc"]: every pair is equal, so the list is trivially sorted. Returns true.
• One word is a prefix of another ["apple", "app"]: "apple" is longer and starts with "app". The shorter word should come first. Returns false.
• Single word ["word"]: no pairs to check. Returns true.
• Empty words list []: no pairs to check. Returns true.
• Two-character differences deep in the word ["app", "apq"]: first two characters match, third character differs. Compare order_map['p'] vs order_map['q'] to decide.
• Reversed alien order order = "zyxwvutsrqponmlkjihgfedcba": words sorted in reverse English order would be correctly sorted here.

Common mistakes

1. Forgetting the prefix case. When one word is a prefix of another (like "apple" and "app"), you need to check that the shorter word comes first. If you only compare character by character and break when you run out of matching characters without this check, you will miss this edge case.

2. Using the wrong comparison direction. It is easy to accidentally check order_map[w1[j]] < order_map[w2[j]] and return False, which reverses the logic. Make sure you return False when the first word's character has a larger index than the second word's character.

3. Comparing all pairs instead of just adjacent pairs. You do not need to compare every word with every other word. If each adjacent pair is sorted, the entire list is sorted. Comparing all pairs would still be correct but wastes time.

4. Rebuilding the order map inside the loop. The order map is the same for every comparison. Build it once before the loop starts. Rebuilding it for each pair is wasteful.

From understanding to recall

You have read the solution and it makes sense. A hash map for the order, a loop over adjacent pairs, and a character-by-character comparison with an early exit. Clean and logical. But when you sit down in an interview and need to write it from memory, the small details trip you up: checking j >= len(w2) for the prefix case, using break after finding a difference, and getting the comparison direction right.

Spaced repetition drills these details into long-term memory. You write the solution from scratch at increasing intervals until the pattern is automatic. After a few rounds, you see "custom alphabet" or "verify sort order" and the code flows out without hesitation.

The index mapping and pairwise comparison patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick on their own.

Related posts

• Valid Anagram - Uses character frequency maps, a related hash map technique
• Group Anagrams - Groups strings by sorted character signature using hash maps
• Custom Sort String - Another problem requiring custom character ordering

CodeBricks breaks the verifying an alien dictionary LeetCode problem into its index mapping and pairwise comparison building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a custom sort verification question shows up in your interview, you do not think about it. You just write it.