Topological Sort — Alien Dictionary
↗ LeetCode: Alien Dictionary · Hard · pattern chapter →
Given words sorted alphabetically in an alien language, return the character order. Return "" if impossible.
Example 1 — words=["wrt","wrf","er","ett","rftt"] → "wertf"Example 2 — words=["z","x"] → "zx"Example 3 — words=["z","x","z"] → "" (cycle)
Constraints — 1 ≤ words.length ≤ 100; 1 ≤ words[i].length ≤ 100; lowercase English. Brute enumerates 26! ≈ 4·10²⁶ character orderings — 10⁹ ops/sec means ~10¹⁰ year (dies before universe end). Topo sort of char-pair graph is O(N·L + 26²) = ~10⁴ ops per input, scales to ~10⁶ ops/sec dictionary validations.
Interview timer00:00
Approach 1 — Trial-and-error permutation
Try every char ordering. O(26!). Absurd baseline.
Approach 2 — Build precedence graph + Kahn's BFS toposort (canonical)
Insight. From each adjacent pair (a, b) in the sorted list, find the first differing char — this is a directed edge a[i] → b[i]. Then topological sort the graph. Return "" if there's a cycle OR if b is a strict prefix of a (invalid ordering).
String alienOrder(String[] words) {
Map<Character, Set<Character>> g = new HashMap<>();
Map<Character, Integer> indeg = new HashMap<>();
for (String w : words) for (char c : w.toCharArray()) indeg.putIfAbsent(c, 0);
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i+1];
if (a.length() > b.length() && a.startsWith(b)) return "";
for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
if (a.charAt(j) != b.charAt(j)) {
g.computeIfAbsent(a.charAt(j), k -> new HashSet<>());
if (g.get(a.charAt(j)).add(b.charAt(j))) indeg.merge(b.charAt(j), 1, Integer::sum);
break;
}
}
}
Queue<Character> q = new ArrayDeque<>();
for (var e : indeg.entrySet()) if (e.getValue() == 0) q.offer(e.getKey());
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
char c = q.poll();
sb.append(c);
for (char nxt : g.getOrDefault(c, Set.of()))
if (indeg.merge(nxt, -1, Integer::sum) == 0) q.offer(nxt);
}
return sb.length() == indeg.size() ? sb.toString() : "";
}Complexity — Time O(C) where C = total characters; Space O(1) (bounded alphabet).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Trial-and-error | O(26!) | O(1) | trivia |
| Kahn's BFS toposort | O(C) | O(1) | canonical |
When to use which
- "Any valid order" → Kahn's BFS.
- "Lex-smallest topological order" → replace queue with min-heap.
- DFS-based alternative → recursion + reverse post-order; same complexity.