-
Notifications
You must be signed in to change notification settings - Fork 0
127 — Alien Dictionary
LeetCode 269 · Hard. You're given a list of words from an alien language, sorted lexicographically according to that language's unknown letter ordering. Derive a valid ordering of the alphabet's letters consistent with the given list. If no valid ordering exists (the input is inconsistent), or the input is itself invalid, return "".
Two adjacent words in sorted order leak exactly one piece of information: the first position where they differ tells you that the letter in the earlier word comes before the letter in the later word, in the alien alphabet. "wrt" before "wrf" tells you nothing about w, r, or the rest of the alphabet — only that at the position where they first diverge, t comes before f. Collect one such constraint from every adjacent pair, and you've built a directed graph of "comes before" relationships between letters. Finding a full alphabet ordering consistent with every constraint is then exactly the topological-sort problem this wiki already knows how to solve — Course Schedule, but the "courses" are letters and the "prerequisites" are letter-order constraints instead of class prerequisites.
There's one trap worth naming up front: if "abc" appears before "ab" in the list, that's invalid — a shorter word that's a strict prefix of an earlier, longer word breaks the definition of lexicographic order (like a dictionary listing "cart" before "car"), and no valid alphabet can explain it.
"Derive an ordering from pairwise comparisons of adjacent sorted items" is the cue for building a directed graph of "comes before" constraints and running topological sort on it — the moment a problem says "sorted according to some unknown rule, recover the rule," reach for this pattern.
Build the "comes before" edges from adjacent word pairs, then run Kahn's algorithm but recompute each candidate letter's in-degree by rescanning the full edge set every round, instead of maintaining a running count (the same brute-force shape as Course Schedule's, chapter 117).
func alienOrderBruteForce(_ words: [String]) -> String {
var uniqueChars = Set<Character>()
for w in words { uniqueChars.formUnion(w) }
var edges = Set<[Character]>() // [before, after] pairs, deduped
for i in 0..<words.count - 1 {
let w1 = Array(words[i]), w2 = Array(words[i + 1])
let minLen = min(w1.count, w2.count)
var foundDiff = false
for j in 0..<minLen {
if w1[j] != w2[j] {
edges.insert([w1[j], w2[j]])
foundDiff = true
break
}
}
if !foundDiff && w1.count > w2.count {
return "" // longer word can't validly precede its own prefix
}
}
var taken: [Character] = []
var used = Set<Character>()
while taken.count < uniqueChars.count {
var found: Character? = nil
for c in uniqueChars.sorted() where !used.contains(c) {
// Recompute: does any remaining edge still require an untaken "before" letter?
let hasUnmetPrereq = edges.contains { edge in edge[1] == c && !used.contains(edge[0]) }
if !hasUnmetPrereq {
found = c
break
}
}
guard let next = found else { return "" } // no valid next letter -> cycle
used.insert(next)
taken.append(next)
}
return String(taken)
}
// smoke test
print(alienOrderBruteForce(["wrt","wrf","er","ett","rftt"])) // "wertf"
print(alienOrderBruteForce(["z","x","z"])) // "" (cycle)Big-O: O(C + V² · E) — O(C) (total characters across all words) to derive the edges, then up to V rounds, each scanning up to V letters, each rescanning up to E edges.
Kahn's algorithm with a maintained in-degree count and adjacency map — each edge is examined exactly once overall, when its source letter is finally taken off the queue.
func alienOrder(_ words: [String]) -> String {
var adjacency: [Character: Set<Character>] = [:]
var indegree: [Character: Int] = [:]
for w in words {
for c in w {
if indegree[c] == nil { indegree[c] = 0 }
if adjacency[c] == nil { adjacency[c] = [] }
}
}
for i in 0..<words.count - 1 {
let w1 = Array(words[i]), w2 = Array(words[i + 1])
let minLen = min(w1.count, w2.count)
var foundDiff = false
for j in 0..<minLen {
if w1[j] != w2[j] {
if !adjacency[w1[j]]!.contains(w2[j]) {
adjacency[w1[j]]!.insert(w2[j])
indegree[w2[j], default: 0] += 1
}
foundDiff = true
break
}
}
if !foundDiff && w1.count > w2.count {
return ""
}
}
var queue = indegree.filter { $0.value == 0 }.map { $0.key }.sorted()
var head = 0
var order: [Character] = []
while head < queue.count {
let c = queue[head]; head += 1
order.append(c)
for next in adjacency[c]!.sorted() {
indegree[next]! -= 1
if indegree[next] == 0 {
queue.append(next)
}
}
}
return order.count == indegree.count ? String(order) : ""
}
// smoke test
print(alienOrder(["wrt","wrf","er","ett","rftt"])) // "wertf"
print(alienOrder(["z","x"])) // "zx"
print(alienOrder(["z","x","z"])) // "" (cycle)
print(alienOrder(["abc","ab"])) // "" (invalid: longer word before its own prefix)Big-O: O(C + V + E) — O(C) to scan all characters and derive edges from adjacent word pairs (C = total characters across words), then O(V + E) for the BFS-style queue processing, with V ≤ 26 and E ≤ 26² bounded by the size of the alphabet regardless of how many words there are.
The edge-derivation step — comparing each adjacent word pair, character by character, until the first difference — is identical in both versions and is genuinely the interesting part of this specific problem. Once the "comes before" graph exists, though, the two approaches diverge exactly like Course Schedule's did: the brute force re-derives "does this letter still have an unmet prerequisite?" by rescanning every edge, every round, while Kahn's algorithm maintains that answer incrementally via indegree, decrementing it the instant a prerequisite letter is actually taken. The one thing worth noticing that's unique to this problem: because the alphabet is capped at 26 letters, V and E are both small constants here — the real cost driver, in both approaches, is C, the total number of characters spent deriving the edges in the first place.
- Graphs — adjacent-word comparisons produce a directed graph of "comes before" constraints between letters; the rest of the problem is graph algorithms applied to that derived graph.
- Topological Sort — recovering a full ordering consistent with a set of pairwise "before" constraints, and detecting when no such ordering exists, is topological sort's exact defining use case.
Alien Dictionary is Course Schedule wearing a disguise — turn each adjacent word pair's first differing letters into a "comes before" edge, then topologically sort the alphabet, returning "" the moment a cycle (or an invalid prefix) shows up.
- Why does comparing only the first differing character between two adjacent words give you a complete, correct constraint — why is it safe (and necessary) to ignore every character after that first difference?
- Walk through why
["abc", "ab"]is invalid but["ab", "abc"]is perfectly fine, in terms of what a real dictionary ordering requires. - This problem caps
Vat 26 andEat26²regardless of how many words are in the input. Why doesn't that make the whole algorithmO(1)— what part of the runtime still genuinely depends on the size ofwords?
⬅️ Previous: Swim in Rising Water · Next: Cheapest Flights Within K Stops ➡️