Introduction
LeetCode 269: Alien Dictionary asks you to determine the order of characters in an alien language given a sorted dictionary of words.
This is a classic example of using topological sorting on a directed graph, where:
- Each character is a node
- Edges represent ordering constraints (i.e., charA → charB)
Problem Statement
Given a list of words sorted lexicographically according to the rules of an unknown alien language, return a string that represents the characters in the correct order.
If the ordering is invalid or multiple valid orderings exist, return any valid one. If no valid ordering exists, return "".
Examples
python
Input: ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Input: ["z", "x"]
Output: "zx"
Input: ["z", "x", "z"]
Output: "" # Invalid, cycle detected
✅ Step-by-Step Solution Using Topological Sort
We’ll use Kahn’s algorithm (BFS) for topological sorting.
🔍 Step 1: Build the Graph
- Initialize:
adj: adjacency list (char → list of next chars)indegree: count of incoming edges for each character- Compare adjacent words, and find the first differing character → This gives an edge from
char1 → char2
🔁 Step 2: Topological Sort (Kahn’s Algorithm)
- Start with characters having zero indegree
- Add them to a queue
- Pop one character at a time:
- Add to result
- Reduce indegree of its neighbors
- Add neighbors with zero indegree to queue
🚨 Step 3: Cycle Detection
If the result length ≠ number of unique characters → return ""
✅ Python Code
python
from collections import defaultdict, deque
def alienOrder(words: list[str]) -> str:
# Step 1: Initialize graph and indegree
adj = defaultdict(set)
indegree = {char: 0 for word in words for char in word}
# Step 2: Build the graph
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
if w1[:min_len] == w2[:min_len] and len(w1) > len(w2):
return "" # Invalid ordering (prefix case)
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in adj[c1]:
adj[c1].add(c2)
indegree[c2] += 1
break
# Step 3: Topological Sort
queue = deque([char for char in indegree if indegree[char] == 0])
res = []
while queue:
char = queue.popleft()
res.append(char)
for neighbor in adj[char]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return "".join(res) if len(res) == len(indegree) else ""
🧪 Example Walkthrough
Input: ["wrt", "wrf", "er", "ett", "rftt"]
- From wrt → wrf →
t < f
- From wrf → er →
w < e
- From er → ett →
r < t
- From ett → rftt →
e < r
Graph edges:
nginx
t → f
w → e
r → t
e → r
Topological sort: w → e → r → t → f
✅ Output: "wertf"
⏱️ Time and Space Complexity
- Time Complexity: O(C)
- where C is the total number of characters in all words
- Space Complexity: O(1)
- since the alphabet size is limited to 26
⚠️ Edge Case Handling
["abc", "ab"] → ❌ invalid, return ""- Duplicate characters: handled via
set
- Multiple valid orders: allowed, return any one
✅ Conclusion
LeetCode 269: Alien Dictionary is a textbook example of how graph theory (especially topological sorting) can be applied to language problems.
You learned:
- How to build character precedence from a dictionary
- How to apply Kahn’s algorithm (BFS) to detect ordering
- How to detect cycles or invalid prefixes