Lesson 168 of 250
269. Alien Dictionary
NeetCode: Alien Dictionary · LeetCode: 269. Alien Dictionary · Difficulty: Hard
Words in an alien language are sorted lexicographically by that language's alphabet. Given the sorted list words (a String[] of lowercase words), return a string of the unique letters in a valid alphabet order, or "" if no valid order exists (the input is contradictory). Any valid order is accepted; the inputs below have a single valid order, so the output is deterministic.
Example
Input: ["hrn", "hrf", "er", "enn", "rfnn"] Output: "hernf"
Input: ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf"
Input: ["z", "o", "z"] Output: "" (z < o and o < z)
Input: ["abc", "ab"] Output: "" (a longer word cannot come before its own prefix)The order between two words is decided by their first differing letter: if a[i] != b[i] at that position, then a[i] comes before b[i] in the alphabet. Those facts are edges of a directed graph on letters, and a valid alphabet is a topological order of it. A cycle means the input is contradictory.
Brute force: derive edges from every pair of words
Compare every pair i < j, extract the first differing letters as an edge, and reject the pair if words[j] is a strict prefix of words[i]. Then topologically sort with Kahn's algorithm (repeatedly emit a letter with no unmet prerequisites). If not all letters can be emitted, there is a cycle.
import java.util.PriorityQueue;
class Solution {
// Adds the edge implied by (a, b), or returns false if the pair is invalid.
private boolean addEdge(String a, String b, boolean[][] edge) {
int len = Math.min(a.length(), b.length());
for (int i = 0; i < len; i++) {
if (a.charAt(i) != b.charAt(i)) {
edge[a.charAt(i) - 'a'][b.charAt(i) - 'a'] = true;
return true;
}
}
return a.length() <= b.length(); // b is a prefix of a: only fine when they are equal
}
private String topoSort(boolean[] present, boolean[][] edge) {
int[] indegree = new int[26];
for (int from = 0; from < 26; from++) {
for (int to = 0; to < 26; to++) {
if (edge[from][to]) indegree[to]++;
}
}
PriorityQueue<Integer> ready = new PriorityQueue<>(); // smallest letter first
for (int l = 0; l < 26; l++) {
if (present[l] && indegree[l] == 0) ready.add(l);
}
StringBuilder order = new StringBuilder();
while (!ready.isEmpty()) {
int l = ready.poll();
order.append((char) ('a' + l));
for (int to = 0; to < 26; to++) {
if (edge[l][to] && --indegree[to] == 0) ready.add(to);
}
}
int letters = 0;
for (boolean p : present) if (p) letters++;
return order.length() == letters ? order.toString() : "";
}
public String alienOrder(String[] words) {
boolean[] present = new boolean[26];
for (String w : words) {
for (char c : w.toCharArray()) present[c - 'a'] = true;
}
boolean[][] edge = new boolean[26][26];
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (!addEdge(words[i], words[j], edge)) return "";
}
}
return topoSort(present, edge);
}
}
public class Main {
static void show(String[] words) {
System.out.println("\"" + new Solution().alienOrder(words) + "\"");
}
public static void main(String[] args) {
show(new String[]{"hrn", "hrf", "er", "enn", "rfnn"});
show(new String[]{"wrt", "wrf", "er", "ett", "rftt"});
show(new String[]{"z", "o", "z"});
show(new String[]{"abc", "ab"});
show(new String[]{"abc"});
}
}"hernf"
"wertf"
""
""
"abc"PriorityQueue is a min-heap, so poll returns the smallest letter index first. That makes the order deterministic. Comparing all pairs costs O(N^2 * L) for N words of length up to L, and most of the resulting edges are already implied by adjacent words (if a < b and b < c, the pair (a, c) adds nothing new). Time: O(N^2 * L + 26^2). Space: O(26^2) for the fixed letter graph.
Optimal: adjacent pairs and topological sort
Because the list is sorted, comparing each word with its neighbour captures every constraint; the order between non-adjacent words follows by transitivity. Steps:
- Collect every letter that appears (letters with no constraints must still be in the answer).
- For each adjacent pair, find the first differing position and add the edge
a[i] -> b[i]. If there is none and the first word is longer, it is an invalid prefix case, so return"". - Kahn's algorithm: count in-degrees, start a queue with all letters of in-degree 0, pop a letter, append it to the answer, and decrement its neighbours, queueing any that reach 0. The queue is an
ArrayDeque, which Java uses for queues (addat the tail,pollfrom the head). - If the answer has fewer letters than exist, there is a cycle, so return
"".
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
public String alienOrder(String[] words) {
boolean[] present = new boolean[26];
for (String w : words) {
for (char c : w.toCharArray()) present[c - 'a'] = true;
}
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < 26; i++) adj.add(new ArrayList<>());
int[] indegree = new int[26];
for (int k = 0; k + 1 < words.length; k++) {
String a = words[k], b = words[k + 1];
int len = Math.min(a.length(), b.length());
int i = 0;
while (i < len && a.charAt(i) == b.charAt(i)) i++;
if (i < len) {
adj.get(a.charAt(i) - 'a').add(b.charAt(i) - 'a');
indegree[b.charAt(i) - 'a']++;
} else if (a.length() > b.length()) {
return ""; // b is a proper prefix of a
}
}
Deque<Integer> queue = new ArrayDeque<>();
for (int l = 0; l < 26; l++) {
if (present[l] && indegree[l] == 0) queue.add(l);
}
StringBuilder order = new StringBuilder();
while (!queue.isEmpty()) {
int l = queue.poll();
order.append((char) ('a' + l));
for (int next : adj.get(l)) {
if (--indegree[next] == 0) queue.add(next);
}
}
int letters = 0;
for (boolean p : present) if (p) letters++;
return order.length() == letters ? order.toString() : "";
}
}
public class Main {
static void show(String[] words) {
System.out.println("\"" + new Solution().alienOrder(words) + "\"");
}
public static void main(String[] args) {
show(new String[]{"hrn", "hrf", "er", "enn", "rfnn"});
show(new String[]{"wrt", "wrf", "er", "ett", "rftt"});
show(new String[]{"z", "o", "z"});
show(new String[]{"abc", "ab"});
show(new String[]{"abc"});
}
}"hernf"
"wertf"
""
""
"abc"Walkthrough of the first example: hrn/hrf gives n < f, hrf/er gives h < e, er/enn gives r < n, enn/rfnn gives e < r. The chain h < e < r < n < f is the only valid order, so the answer is hernf. Duplicate edges are harmless: the in-degree is incremented once per copy and decremented once per copy. Time: O(total characters + 26). Space: O(26 + edges), effectively constant because the alphabet is fixed.
How to explain it in an interview
- Brute force: compare every pair of words, take the first differing letters as edges, then topologically sort. That is
O(N^2 * L)comparisons. - Key idea: the list is sorted, so adjacent pairs give all the information. The alphabet order is a topological order of the letter graph, and a cycle means there is no valid order.
- Steps: (1) mark the letters present; (2) for each adjacent pair add one edge, or return
""for the bad-prefix case ("abc"before"ab"); (3) compute in-degrees; (4) run Kahn's algorithm with a queue; (5) compare the output length with the number of letters to detect a cycle. - Complexity: time
O(total characters)(the alphabet has 26 letters), spaceO(1)for a fixed alphabet. - Pitfalls: letters that appear in no edge must still be output, and the prefix case must be handled. Any valid order is accepted; a smallest-first heap makes the output deterministic.