Alien Dictionary

LeetCode 269: Alien Dictionary Solution & Explanation

Problem Overview

TL;DR: Construct a directed graph where edges represent character precedence derived from adjacent words, then perform a Topological Sort using Kahn's Algorithm (BFS) to determine the linear order.

The LeetCode 269 Alien Dictionary problem asks us to reconstruct the alphabet order of an unknown language. We are provided with a list of words sorted lexicographically according to this alien language's rules. By analyzing the relative order of characters in adjacent words, we must derive a valid sequence of all characters present. If the input contains contradictions (cycles) or invalid prefix ordering, we must return an empty string. This is a classic problem frequently seen in technical interviews at top tech companies.

Brute Force Approach for Alien Dictionary

A naive brute force approach would attempt to generate every possible permutation of the unique characters found in the input list and verify if the given words list is sorted according to that specific permutation.

1. Extract all unique characters from the input words.
2. Generate all permutations of these characters (e.g., if characters are {a, b, c}, generate abc, acb, bac, etc.).
3. For each permutation, define a custom comparator that uses this specific order.
4. Check if the input words array is sorted based on this comparator.
5. Return the first permutation that satisfies the sort order.

Time Complexity Analysis: If there are $U$ unique characters, there are $U!$ permutations. Checking if the list is sorted takes $O(N \cdot L)$, where $N$ is the number of words and $L$ is the maximum length of a word. The total complexity is $O(U! \cdot N \cdot L)$. Given that $U$ can be up to 26 (lowercase English letters), $26!$ is an astronomically large number. This approach is computationally infeasible and will immediately result in a Time Limit Exceeded (TLE) error. Furthermore, it does not efficiently detect specific invalid states like cycles.

Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)

We will implement Kahn's Algorithm to solve LeetCode 269. The strategy involves three main phases: Graph Construction, Initialization, and BFS Processing.

1. Data Structures:

   • Adjacency List (adj): A map where keys are characters and values are sets of characters that come immediately after.
   • In-degree Map (counts): A map tracking the number of incoming edges for each character. Every unique character must have an entry in this map, initialized to 0.

2. Graph Construction:

   • Iterate through the words list, comparing adjacent words (words[i] and words[i+1]).
   • Find the first index j where the characters differ.
   • If a difference is found (e.g., c1 != c2), add a directed edge $c1 \to c2$ to the adjacency list and increment the in-degree of c2.
   • Constraint Check: If words[i+1] is a prefix of words[i] (e.g., "apple", "app"), the input is invalid because the shorter word should come first. Return an empty string immediately.

3. BFS Initialization:

   • Create a queue.
   • Add all characters with an in-degree of 0 to the queue. These characters have no dependencies and can be the start of the alphabet.

4. BFS Execution:

   • While the queue is not empty:
     • Dequeue the current character curr.
     • Append curr to the result string.
     • Iterate through all neighbors of curr in the adjacency list.
     • Decrement the in-degree of each neighbor.
     • If a neighbor's in-degree becomes 0, enqueue it.

5. Validation:

   • Compare the length of the result string with the total number of unique characters.
   • If lengths match, return the result string.
   • If lengths do not match, a cycle exists. Return an empty string.

Execution Flow

Let's trace the algorithm with input: words = ["wrt","wrf","er","ett","rftt"].

1. Initialization:

   • Unique chars: {w, r, t, f, e}.
   • counts map initialized to 0 for all.

2. Building Graph:

   • Compare "wrt", "wrf": mismatch at 't', 'f'. Edge t -> f. counts[f] = 1.
   • Compare "wrf", "er": mismatch at 'w', 'e'. Edge w -> e. counts[e] = 1.
   • Compare "er", "ett": mismatch at 'r', 't'. Edge r -> t. counts[t] = 1.
   • Compare "ett", "rftt": mismatch at 'e', 'r'. Edge e -> r. counts[r] = 1.
   • Graph: t->f, w->e, r->t, e->r.
   • In-degrees: w:0, r:1, t:1, f:1, e:1.

3. Queue Processing:

   • Queue: [w] (only 'w' has 0 in-degree).
   • Pop 'w': Result = "w". Neighbors: e.
     • Decrement counts[e] to 0. Add e to Queue.
   • Queue: [e].
   • Pop 'e': Result = "we". Neighbors: r.
     • Decrement counts[r] to 0. Add r to Queue.
   • Queue: [r].
   • Pop 'r': Result = "wer". Neighbors: t.
     • Decrement counts[t] to 0. Add t to Queue.
   • Queue: [t].
   • Pop 't': Result = "wert". Neighbors: f.
     • Decrement counts[f] to 0. Add f to Queue.
   • Queue: [f].
   • Pop 'f': Result = "wertf". Neighbors: none.

4. Final Check:

   • Result length is 5. Total unique chars is 5.
   • Return "wertf".

Proof of Correctness

The algorithm relies on the property of Directed Acyclic Graphs (DAGs). A topological sort is only possible if and only if the graph is a DAG.

1. Invariant: At any step, the queue contains only characters whose prerequisites (incoming edges) have all been satisfied (processed and added to result).
2. Progress: By removing a node and its outgoing edges, we effectively solve the sub-problem for the remaining graph.
3. Cycle Detection: If a cycle exists (e.g., $A \to B \to A$), the in-degrees of nodes in the cycle will never reach 0 because they are mutually dependent. Consequently, they will never enter the queue, and the final result length will be less than the total number of unique characters.

Pattern Reuse Notes

The Graph BFS - Topological Sort (Kahn's Algorithm) pattern used in this LeetCode 269 Solution is highly versatile. It applies directly to:

• LeetCode 207: Course Schedule (Detecting if a valid schedule exists is cycle detection).
• LeetCode 210: Course Schedule II (Returning the actual schedule is exactly Topological Sort).
• LeetCode 310: Minimum Height Trees (Uses a similar "peeling onion" strategy with degrees).
• LeetCode 444: Sequence Reconstruction (Verifying if a topological sort is unique).

Mastering Kahn's Algorithm allows you to solve any problem involving dependency resolution or precedence ordering.

Reference Implementation

C++ Solution for LeetCode 269

1class Solution {
2public:
3    string alienOrder(vector<string>& words) {
4        unordered_map<char, unordered_set<char>> adj;
5        unordered_map<char, int> counts;
6        
7        // 1. Initialize counts for all unique characters
8        for (const string& word : words) {
9            for (char c : word) {
10                counts[c] = 0;
11            }
12        }
13        
14        // 2. Build the graph
15        for (int i = 0; i < words.size() - 1; ++i) {
16            string w1 = words[i];
17            string w2 = words[i+1];
18            
19            // Check for invalid prefix condition (e.g., "abc" before "ab")
20            if (w1.size() > w2.size() && w1.substr(0, w2.size()) == w2) {
21                return "";
22            }
23            
24            // Find the first differing character
25            for (int j = 0; j < min(w1.size(), w2.size()); ++j) {
26                if (w1[j] != w2[j]) {
27                    if (adj[w1[j]].find(w2[j]) == adj[w1[j]].end()) {
28                        adj[w1[j]].insert(w2[j]);
29                        counts[w2[j]]++;
30                    }
31                    break; // Only the first difference determines order
32                }
33            }
34        }
35        
36        // 3. BFS (Kahn's Algorithm)
37        queue<char> q;
38        for (auto& entry : counts) {
39            if (entry.second == 0) {
40                q.push(entry.first);
41            }
42        }
43        
44        string result = "";
45        while (!q.empty()) {
46            char curr = q.front();
47            q.pop();
48            result += curr;
49            
50            if (adj.count(curr)) {
51                for (char neighbor : adj[curr]) {
52                    counts[neighbor]--;
53                    if (counts[neighbor] == 0) {
54                        q.push(neighbor);
55                    }
56                }
57            }
58        }
59        
60        // 4. Check for cycles
61        if (result.size() < counts.size()) {
62            return "";
63        }
64        
65        return result;
66    }
67};

Java Solution for LeetCode 269

1import java.util.*;
2
3class Solution {
4    public String alienOrder(String[] words) {
5        Map<Character, Set<Character>> adj = new HashMap<>();
6        Map<Character, Integer> counts = new HashMap<>();
7        
8        // 1. Initialize counts for all unique characters
9        for (String word : words) {
10            for (char c : word.toCharArray()) {
11                counts.put(c, 0);
12            }
13        }
14        
15        // 2. Build the graph
16        for (int i = 0; i < words.length - 1; i++) {
17            String w1 = words[i];
18            String w2 = words[i+1];
19            
20            // Check for invalid prefix condition (e.g., "abc" before "ab")
21            if (w1.length() > w2.length() && w1.startsWith(w2)) {
22                return "";
23            }
24            
25            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
26                if (w1.charAt(j) != w2.charAt(j)) {
27                    char u = w1.charAt(j);
28                    char v = w2.charAt(j);
29                    
30                    adj.putIfAbsent(u, new HashSet<>());
31                    if (adj.get(u).add(v)) {
32                        counts.put(v, counts.get(v) + 1);
33                    }
34                    break; // Only the first difference matters
35                }
36            }
37        }
38        
39        // 3. BFS (Kahn's Algorithm)
40        Queue<Character> queue = new LinkedList<>();
41        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
42            if (entry.getValue() == 0) {
43                queue.offer(entry.getKey());
44            }
45        }
46        
47        StringBuilder result = new StringBuilder();
48        while (!queue.isEmpty()) {
49            char curr = queue.poll();
50            result.append(curr);
51            
52            if (adj.containsKey(curr)) {
53                for (char neighbor : adj.get(curr)) {
54                    counts.put(neighbor, counts.get(neighbor) - 1);
55                    if (counts.get(neighbor) == 0) {
56                        queue.offer(neighbor);
57                    }
58                }
59            }
60        }
61        
62        // 4. Check for cycles
63        if (result.length() < counts.size()) {
64            return "";
65        }
66        
67        return result.toString();
68    }
69}

Python Solution for LeetCode 269

1from collections import deque, defaultdict
2
3class Solution:
4    def alienOrder(self, words: list[str]) -> str:
5        adj = defaultdict(set)
6        counts = {c: 0 for word in words for c in word}
7        
8        # 1. Build the graph
9        for i in range(len(words) - 1):
10            w1, w2 = words[i], words[i + 1]
11            
12            # Check for invalid prefix (e.g., "abc" before "ab")
13            if len(w1) > len(w2) and w1.startswith(w2):
14                return ""
15            
16            for c1, c2 in zip(w1, w2):
17                if c1 != c2:
18                    if c2 not in adj[c1]:
19                        adj[c1].add(c2)
20                        counts[c2] += 1
21                    break
22        
23        # 2. BFS (Kahn's Algorithm)
24        queue = deque([c for c in counts if counts[c] == 0])
25        result = []
26        
27        while queue:
28            curr = queue.popleft()
29            result.append(curr)
30            
31            for neighbor in adj[curr]:
32                counts[neighbor] -= 1
33                if counts[neighbor] == 0:
34                    queue.append(neighbor)
35        
36        # 3. Check for cycles
37        if len(result) < len(counts):
38            return ""
39            
40        return "".join(result)