Verifying an Alien Dictionary — Problem & Solution
Verifying an Alien Dictionary solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Verifying an Alien Dictionary is an easy coding problem on arrays, strings and hash table, asked in Amazon, Google and Meta interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An alien language uses the English letters but in a different alphabetical order, given by the permutation order.
Return true if words is sorted lexicographically according to that order.
Example 1
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: h precedes l in this alphabet.
Example 2
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: "word" comes after "world" because d follows l here.
Example 3
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: A prefix must come before the longer word.
Constraints
1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26All characters are lowercase English letters and order is a permutation of them.
Hints for Verifying an Alien Dictionary
Hint 1
Turn the alphabet string into a rank lookup:
rank[c]is the position ofcinorder.Hint 2
Comparing two words means finding the first index where they differ and comparing ranks there.
Hint 3
If neither differs before one ends, the shorter word must come first.
How to solve Verifying an Alien Dictionary
Re-mapping each letter to its rank in the alien alphabet reduces the problem to ordinary lexicographic comparison of adjacent word pairs.
Approach
- Build
rankfromorder, mapping each letter to its index. - For each adjacent pair
(a, b), scan to the first position where they differ. - If such a position exists, the pair is in order iff
rank[a[i]] < rank[b[i]]. - If no position differs, the pair is in order iff
a.length <= b.length. - Return
falseon the first violation,trueotherwise.
Why it works
Lexicographic order is a total order, so checking only adjacent pairs is sufficient — sortedness is a chain of pairwise comparisons.
Complexity
- Time —
O(total characters) - Space —
O(1) — the rank table is 26 entries
Pitfalls
- Missing the prefix rule marks
["apple","app"]as sorted. - Comparing the raw strings with the language's built-in comparison ignores
orderentirely. - Comparing all pairs instead of adjacent ones is O(n²) for no benefit.
Reference solution
Python
from typing import List
def isAlienSorted(words: List[str], order: str) -> bool:
rank = {c: i for i, c in enumerate(order)}
def le(a, b):
for x, y in zip(a, b):
if x != y:
return rank[x] < rank[y]
return len(a) <= len(b)
for i in range(len(words) - 1):
if not le(words[i], words[i + 1]):
return False
return TrueJava
public static boolean isAlienSorted(String[] words, String order) {
int[] rank = new int[26];
for (int i = 0; i < order.length(); i++) rank[order.charAt(i) - 'a'] = i;
for (int w = 0; w + 1 < words.length; w++) {
String a = words[w], b = words[w + 1];
int n = Math.min(a.length(), b.length());
boolean decided = false;
for (int i = 0; i < n; i++) {
if (a.charAt(i) != b.charAt(i)) {
if (rank[a.charAt(i) - 'a'] > rank[b.charAt(i) - 'a']) return false;
decided = true;
break;
}
}
if (!decided && a.length() > b.length()) return false;
}
return true;
}C++
bool isAlienSorted(vector<string>& words, string order) {
int rank[26];
for (int i = 0; i < (int) order.size(); i++) rank[order[i] - 'a'] = i;
for (int w = 0; w + 1 < (int) words.size(); w++) {
const string& a = words[w];
const string& b = words[w + 1];
int n = (int) min(a.size(), b.size());
bool decided = false;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
if (rank[a[i] - 'a'] > rank[b[i] - 'a']) return false;
decided = true;
break;
}
}
if (!decided && a.size() > b.size()) return false;
}
return true;
}JavaScript
var isAlienSorted = function(words, order) {
const rank = {};
for (let i = 0; i < order.length; i++) rank[order.charAt(i)] = i;
function le(a, b) {
const n = Math.min(a.length, b.length);
for (let i = 0; i < n; i++) {
if (a.charAt(i) !== b.charAt(i)) return rank[a.charAt(i)] < rank[b.charAt(i)];
}
return a.length <= b.length;
}
for (let i = 0; i + 1 < words.length; i++) {
if (!le(words[i], words[i + 1])) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.