Coding Interview PatternsVerifying an Alien Dictionary
EasyTopological Sort

Verifying an Alien Dictionary

Explanation & Solution

Practice Problem

Description

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

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

Input:words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
0
hello
1
leetcode

Output: true

Explanation: As 'h' comes before 'l' in this language, the sequence is sorted.

Constraints

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

Approach

Topological Sort pattern

1. Build the Order Map

  • Create a map from each character to its position in the alien alphabet
  • For example, if order = "hlabcdefgijkmnopqrstuvwxyz", then h → 0, l → 1, a → 2, etc.
  • This allows O(1) comparison of any two characters

2. Compare Adjacent Word Pairs

  • Iterate through each consecutive pair of words (words[i], words[i+1])
  • Compare them character by character to determine their relative order

3. Find the First Differing Character

  • Walk through both words up to the length of the shorter one
  • At the first position where characters differ, check their order in the alien alphabet
  • If w1's character has a higher rank than w2's, the words are not sorted — return false
  • If w1's character has a lower rank, this pair is correctly ordered — move to the next pair

4. Handle the Prefix Case

  • If all compared characters are equal but w1 is longer than w2, the order is invalid
  • A prefix must always come before the longer word in lexicographic order

5. Return the Result

  • If all adjacent pairs are correctly ordered, return true

Key Insight

  • This problem reduces to comparing adjacent pairs — if every consecutive pair is in order, the entire list is sorted
  • The alien alphabet is handled by mapping characters to indices, turning character comparison into integer comparison
  • The prefix edge case (e.g., "apple" before "app") is a common trap
Time
O(M) where M is the total number of characters across all words
Space
O(1) since the order map has at most 26 entries

Solution Code

Previous
Compilation Order
Next
Find All Possible Recipes from Given Supplies