HardBlind75GraphTopological Sort
Alien Dictionary
Given a sorted list of words in an alien language, find the order of characters in that language.
Examples
Input
words = ["wrt","wrf","er","ett","rftt"]
Output
"wertf"
From the given words, we can deduce: w < e < r < t < f.
Input
words = ["z","x"]
Output
zx
From 'z' before 'x', we know z < x.
Constraints
- •
1 <= words.length <= 100 - •
1 <= words[i].length <= 100 - •
words[i] consists of only lowercase English letters. - •
All strings in words are unique.
Approaches
Compare adjacent words to find character ordering relationships.
CodeT: O(C) | S: O(C)
from collections import defaultdict, deque
def alien_order(words):
adj = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return ''
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]:
adj[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(in_degree):
return ''
return ''.join(result)Build graph from word comparisons, then topological sort.
CodeT: O(C) | S: O(C)
from collections import defaultdict, deque
def alien_order(words):
adj = defaultdict(set)
in_degree = {}
for word in words:
for c in word:
in_degree[c] = 0
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]:
adj[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
else:
if len(w1) > len(w2):
return ''
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return ''.join(result) if len(result) == len(in_degree) else ''Same approach with cleaner implementation.
Diagram
words = ['wrt','wrf','er','ett','rftt']
wrt vs wrf: t != f -> t < f
wrf vs er: w != e -> w < e
er vs ett: r != t -> r < t
ett vs rftt: e != r -> e < r
Order: w < e < r < t < f -> 'wertf'
CodeT: O(C) | S: O(C)
from collections import defaultdict, deque
def alien_order(words):
graph = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for w1, w2 in zip(words, words[1:]):
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in graph[c1]:
graph[c1].add(c2)
in_degree[c2] += 1
break
else:
if len(w1) > len(w2):
return ''
queue = deque([c for c in in_degree if in_degree[c] == 0])
order = []
while queue:
c = queue.popleft()
order.append(c)
for neighbor in graph[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return ''.join(order) if len(order) == len(in_degree) else ''Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Compare Adjacent Words | O(C) | O(C) | Compare adjacent words to find character ordering relationships. |
| Topological Sort - BFS | O(C) | O(C) | Build graph from word comparisons, then topological sort. |
| Optimized Topological Sort | O(C) | O(C) | Same approach with cleaner implementation. |
Compare Adjacent Words
T: O(C)S: O(C)
Compare adjacent words to find character ordering relationships.
Topological Sort - BFS
T: O(C)S: O(C)
Build graph from word comparisons, then topological sort.
Optimized Topological Sort
T: O(C)S: O(C)
Same approach with cleaner implementation.
Common Mistakes
Not handling the case where a longer word comes before a shorter word with same prefix
Using DFS instead of BFS for topological sort (both work but BFS is simpler)
Not detecting cycles in the character ordering