Verifying an Alien Dictionary
Easy · Arrays & Hashing · Array · Hash Table · String
Problem
An alien language writes with the same 26 lowercase letters as English, but in a different order. That order is given as order, a permutation of the alphabet, and words is a list of words in the alien language.
Return true if words is sorted in the alien dictionary order, and false otherwise.
Two words compare at the first position where they differ: the word whose letter ranks earlier in order comes first. If one word is a prefix of the other, the shorter word must come first.
Examples
Input: words = ["cab","cat","ba"], order = "cbatdefghijklmnopqrsuvwxyz" Output: true
"cab" < "cat" because 'b' ranks before 't', and "cat" < "ba" because 'c' ranks before 'b'.
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false
"app" is a prefix of "apple", so it must come first.
Input: words = ["zx","zy"], order = "zyxwvutsrqponmlkjihgfedcba" Output: false
In this order 'y' ranks before 'x'.
Constraints
- 1 <= len(words) <= 100
- 1 <= len(words[i]) <= 20
- len(order) == 26
- All letters in words and order are lowercase English letters
- order is a permutation of the alphabet
Approaches
- Baseline: translate, sort and compare — time O(C log n), space O(C)
Follow-up
The reverse question, recovering the alphabet from a sorted word list, turns each first difference into an edge x → y and asks for a topological order of the letters (the separate problem Alien Dictionary). Here the order is given, so a lookup table is all you need.
Related problems
Start free on Cariara · Coding problems · System design studio
