LeetCode 953 - Verifying an Alien Dictionary

This problem asks us to verify whether a list of words is sorted according to a custom alphabet order, instead of the normal English alphabetical order. In normal lexicographical ordering, characters are compared from left to right using the standard alphabet.

leetcodeeasyarrayhash-tablestring

LeetCode Problem 953

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String

Solution

Problem Understanding

This problem asks us to verify whether a list of words is sorted according to a custom alphabet order, instead of the normal English alphabetical order.

In normal lexicographical ordering, characters are compared from left to right using the standard alphabet. Here, the alien language still uses lowercase English letters, but the relative order of those letters may be completely different. The order string tells us the ranking of each character in this alien language.

The input consists of:

  • words, an array of strings written in the alien language
  • order, a string of length 26 that defines the alien alphabet ordering

The goal is to determine whether the words are already sorted according to this custom lexicographical order.

Lexicographical comparison works exactly like dictionary comparison:

  • Compare characters one by one from left to right
  • The first differing character determines which word is smaller
  • If all compared characters are identical, then the shorter word is considered smaller

For example:

  • "app" comes before "apple"
  • "apple" does not come before "app"

The constraints are relatively small:

  • At most 100 words
  • Each word has length at most 20
  • Only lowercase English letters are used

These limits tell us that performance is not extremely critical, but we should still design a clean and efficient solution. Since the alphabet size is fixed at 26, building a lookup table for character rankings is very cheap.

Several edge cases are especially important:

  • One word may be a prefix of another
  • The first differing character may appear very late in the strings
  • Adjacent words may be identical
  • The alien ordering may differ drastically from normal English order

A naive implementation can easily fail on prefix cases like ["apple", "app"], where all shared characters match but the longer word incorrectly appears first.

Approaches

Brute Force Approach

A brute force solution would simulate lexicographical comparison directly for every adjacent pair of words.

For each pair:

  1. Compare characters one by one
  2. Find the first differing character
  3. Determine ordering using the alien alphabet
  4. If no differing character exists, compare word lengths

To determine character ordering, the brute force method could repeatedly search through the order string using operations like order.index(char) whenever characters are compared.

This works correctly because lexicographical ordering only depends on the first differing character. However, repeatedly scanning the order string is inefficient because every character lookup costs O(26) time.

Even though the constraints are small, this repeated searching is unnecessary.

Optimal Approach

The key insight is that character comparisons happen frequently, so we should preprocess the alien alphabet into a direct lookup structure.

We create a hash map:

character -> rank

For example:

h -> 0
l -> 1
a -> 2
...

Now each character comparison becomes O(1) instead of scanning the entire alphabet string.

We then compare every adjacent pair of words lexicographically using these ranks.

This gives a clean and efficient solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(N × M × 26) O(1) Repeatedly scans the order string for character ranking
Optimal O(N × M) O(26) Uses hash map for constant time character ranking

Where:

  • N = number of words
  • M = maximum word length

Algorithm Walkthrough

  1. Create a hash map called rank.

This map stores the position of each character in the alien alphabet.

For example:

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

This allows constant time comparisons between characters. 2. Iterate through all adjacent pairs of words.

Since a sorted list only requires every neighboring pair to be correctly ordered, we compare:

words[0] vs words[1]
words[1] vs words[2]
...
  1. Compare the two words character by character.

Use a loop over the minimum length of the two words.

At each position:

  • If characters are equal, continue

  • If characters differ:

  • Compare their alien ranks

  • If the first word's character has a larger rank, return False

  • Otherwise, the pair is correctly ordered, so stop checking this pair

  1. Handle the prefix case.

If all compared characters match, then ordering depends entirely on length.

Example:

"app" < "apple"

If the first word is longer after all shared characters match, the ordering is invalid. 5. If all adjacent pairs are valid, return True.

Why it works

Lexicographical ordering is determined entirely by the first differing character between two strings. If all characters match up to the shorter word's length, then the shorter word must come first.

The algorithm directly implements this rule for every adjacent pair of words. Since a sequence is sorted if and only if every neighboring pair is sorted, checking all adjacent pairs guarantees correctness.

Python Solution

from typing import List

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]

            found_difference = False

            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    if rank[word1[j]] > rank[word2[j]]:
                        return False

                    found_difference = True
                    break

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

        return True

The implementation begins by constructing the rank dictionary. This preprocessing step converts the alien alphabet into constant time lookups.

The outer loop iterates through adjacent pairs of words because verifying every neighboring pair is sufficient to confirm the entire list is sorted.

For each pair, the inner loop compares characters position by position.

If the characters differ, their alien ranks determine ordering immediately. If the first word contains a character with a larger rank, the list is not sorted, so the function returns False.

The variable found_difference tracks whether a mismatch was encountered. This is important for handling prefix cases correctly. If no differing character exists and the first word is longer, then the ordering is invalid.

If all pairs pass the checks, the function returns True.

Go Solution

func isAlienSorted(words []string, order string) bool {
	rank := make(map[byte]int)

	for i := 0; i < len(order); i++ {
		rank[order[i]] = i
	}

	for i := 0; i < len(words)-1; i++ {
		word1 := words[i]
		word2 := words[i+1]

		foundDifference := false

		minLength := len(word1)
		if len(word2) < minLength {
			minLength = len(word2)
		}

		for j := 0; j < minLength; j++ {
			if word1[j] != word2[j] {
				if rank[word1[j]] > rank[word2[j]] {
					return false
				}

				foundDifference = true
				break
			}
		}

		if !foundDifference && len(word1) > len(word2) {
			return false
		}
	}

	return true
}

The Go implementation follows the same logic as the Python version.

One notable difference is that Go strings are indexed as bytes, which works perfectly here because the problem guarantees lowercase English letters only.

Go does not provide a built in min() function for integers in older versions, so the minimum length is computed manually.

The hash map uses map[byte]int because characters are represented as bytes.

Worked Examples

Example 1

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

Step 1: Build rank map

Character Rank
h 0
l 1
a 2
b 3
c 4

Remaining characters continue similarly.

Step 2: Compare "hello" and "leetcode"

Position word1 word2 Comparison
0 h l h < l

Since rank['h'] < rank['l'], the ordering is valid.

Result:

True

Example 2

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

Compare "word" and "world"

Position word1 word2 Comparison
0 w w equal
1 o o equal
2 r r equal
3 d l d > l

Since d comes after l in the alien alphabet, ordering is invalid.

Result:

False

Example 3

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

Compare "apple" and "app"

Position word1 word2 Comparison
0 a a equal
1 p p equal
2 p p equal

No differing character exists.

Now compare lengths:

Word Length
apple 5
app 3

The first word is longer, so ordering is invalid.

Result:

False

Complexity Analysis

Measure Complexity Explanation
Time O(N × M) Each character of each adjacent word pair is compared at most once
Space O(26) The rank map stores one entry per lowercase letter

The preprocessing step for the alien alphabet costs only O(26), which is effectively constant.

The main work comes from comparing adjacent words. In the worst case, every character of every word participates in comparisons, giving O(N × M) complexity.

The extra space usage is constant because the alphabet size never exceeds 26 letters.

Test Cases

from typing import List

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]

            found_difference = False

            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    if rank[word1[j]] > rank[word2[j]]:
                        return False

                    found_difference = True
                    break

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

        return True

solution = Solution()

assert solution.isAlienSorted(
    ["hello", "leetcode"],
    "hlabcdefgijkmnopqrstuvwxyz"
) == True  # basic valid ordering

assert solution.isAlienSorted(
    ["word", "world", "row"],
    "worldabcefghijkmnpqstuvxyz"
) == False  # differing character causes invalid order

assert solution.isAlienSorted(
    ["apple", "app"],
    "abcdefghijklmnopqrstuvwxyz"
) == False  # prefix edge case

assert solution.isAlienSorted(
    ["app", "apple"],
    "abcdefghijklmnopqrstuvwxyz"
) == True  # shorter prefix first is valid

assert solution.isAlienSorted(
    ["a", "b", "c"],
    "abcdefghijklmnopqrstuvwxyz"
) == True  # simple sorted sequence

assert solution.isAlienSorted(
    ["c", "b", "a"],
    "abcdefghijklmnopqrstuvwxyz"
) == False  # reverse sorted sequence

assert solution.isAlienSorted(
    ["same", "same"],
    "abcdefghijklmnopqrstuvwxyz"
) == True  # identical adjacent words

assert solution.isAlienSorted(
    ["z", "x"],
    "zyxwvutsrqponmlkjihgfedcba"
) == True  # custom reverse alphabet

assert solution.isAlienSorted(
    ["aa", "aaa"],
    "abcdefghijklmnopqrstuvwxyz"
) == True  # prefix with increasing length

assert solution.isAlienSorted(
    ["aaa", "aa"],
    "abcdefghijklmnopqrstuvwxyz"
) == False  # invalid prefix ordering
Test Why
["hello","leetcode"] Verifies standard valid alien ordering
["word","world","row"] Verifies detection of invalid character ordering
["apple","app"] Tests critical prefix edge case
["app","apple"] Verifies valid prefix ordering
["a","b","c"] Tests simple increasing order
["c","b","a"] Tests clearly invalid order
["same","same"] Verifies identical words are accepted
["z","x"] with reversed alphabet Tests non standard alphabet ranking
["aa","aaa"] Valid prefix relationship
["aaa","aa"] Invalid prefix relationship

Edge Cases

Prefix Relationships

One of the most important edge cases occurs when one word is a prefix of another.

For example:

["apple", "app"]

All shared characters match, so the shorter word should come first. A naive implementation that only compares differing characters may incorrectly accept this ordering.

The implementation explicitly checks whether all compared characters matched and whether the first word is longer. If both are true, it returns False.

Identical Words

Adjacent words may be exactly the same.

For example:

["same", "same"]

No differing character exists, but the lengths are equal, so the ordering is valid.

The implementation handles this naturally because the prefix check only fails when the first word is strictly longer.

Custom Alphabet Order

The alien alphabet may differ completely from standard English ordering.

For example:

order = "zyxwvutsrqponmlkjihgfedcba"

In this language, 'z' is the smallest character.

A solution that accidentally relies on normal ASCII ordering would fail. The implementation avoids this issue entirely by always comparing characters using the precomputed rank map instead of direct character comparison.