BFS Topological Sort (Kahn's Algorithm)
Intuition
The key insight is that comparing adjacent words reveals ordering constraints between characters. If two adjacent words share a prefix but differ at position k, then the character at position k in the first word comes before the character at position k in the second word. We build a directed graph of these character orderings and perform a topological sort. If the sort includes all characters, we have a valid ordering. If not, there is a contradiction (cycle). We use BFS (Kahn's algorithm) for the topological sort: start with characters that have no incoming edges and process layer by layer.
Algorithm
- Collect all unique characters from all words. Initialize in-degree to 0 for each.
- Compare each pair of adjacent words. Find the first position where characters differ -- this gives an edge from the first character to the second. If a longer word appears before its prefix, return "" (invalid).
- Build an adjacency list and compute in-degrees from these edges.
- Add all characters with in-degree 0 to a queue.
- Process the queue: dequeue a character, append to result, and decrement in-degrees of its neighbors. Enqueue neighbors that reach in-degree 0.
- If the result length equals the number of unique characters, return it. Otherwise, return "" (cycle detected).
Time
O(C) where C is the total length of all words combinedSpaceO(1) since the alphabet size is bounded (at most 26 characters)Code (C++ · Java · Python · Go)
class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> graph;
unordered_map<char, int> indegree;
for (const string& word : words) {
for (char c : word) {
indegree[c] = 0;
}
}
for (int i = 0; i + 1 < (int)words.size(); i++) {
string& w1 = words[i];
string& w2 = words[i + 1];
int minLen = min(w1.size(), w2.size());
if (w1.size() > w2.size() && w1.substr(0, minLen) == w2.substr(0, minLen)) {
return "";
}
for (int j = 0; j < minLen; j++) {
if (w1[j] != w2[j]) {
if (!graph[w1[j]].count(w2[j])) {
graph[w1[j]].insert(w2[j]);
indegree[w2[j]]++;
}
break;
}
}
}
queue<char> q;
for (auto& [c, deg] : indegree) {
if (deg == 0) q.push(c);
}
string result;
while (!q.empty()) {
char c = q.front();
q.pop();
result += c;
for (char neighbor : graph[c]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return result.size() == indegree.size() ? result : "";
}
};class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
for (String word : words) {
for (char c : word.toCharArray()) {
indegree.put(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i], w2 = words[i + 1];
int minLen = Math.min(w1.length(), w2.length());
if (w1.length() > w2.length() && w1.substring(0, minLen).equals(w2.substring(0, minLen))) {
return "";
}
for (int j = 0; j < minLen; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
graph.putIfAbsent(w1.charAt(j), new HashSet<>());
if (graph.get(w1.charAt(j)).add(w2.charAt(j))) {
indegree.put(w2.charAt(j), indegree.get(w2.charAt(j)) + 1);
}
break;
}
}
}
Queue<Character> queue = new LinkedList<>();
for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {
if (entry.getValue() == 0) queue.add(entry.getKey());
}
StringBuilder result = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
result.append(c);
if (graph.containsKey(c)) {
for (char neighbor : graph.get(c)) {
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0) {
queue.add(neighbor);
}
}
}
}
return result.length() == indegree.size() ? result.toString() : "";
}
}from typing import List
from collections import deque, defaultdict
class Solution:
def alienOrder(self, words: List[str]) -> str:
graph = defaultdict(set)
indegree = {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 graph[w1[j]]:
graph[w1[j]].add(w2[j])
indegree[w2[j]] += 1
break
queue = deque(c for c in indegree if indegree[c] == 0)
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in graph[c]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return "".join(result) if len(result) == len(indegree) else ""func alienOrder(words []string) string {
graph := make(map[byte]map[byte]bool)
indegree := make(map[byte]int)
for _, word := range words {
for i := 0; i < len(word); i++ {
indegree[word[i]] = indegree[word[i]]
}
}
for i := 0; i < len(words)-1; i++ {
w1, w2 := words[i], words[i+1]
minLen := len(w1)
if len(w2) < minLen {
minLen = len(w2)
}
if len(w1) > len(w2) && w1[:minLen] == w2[:minLen] {
return ""
}
for j := 0; j < minLen; j++ {
if w1[j] != w2[j] {
if graph[w1[j]] == nil {
graph[w1[j]] = make(map[byte]bool)
}
if !graph[w1[j]][w2[j]] {
graph[w1[j]][w2[j]] = true
indegree[w2[j]]++
}
break
}
}
}
queue := []byte{}
for c, deg := range indegree {
if deg == 0 {
queue = append(queue, c)
}
}
result := []byte{}
for len(queue) > 0 {
c := queue[0]
queue = queue[1:]
result = append(result, c)
for neighbor := range graph[c] {
indegree[neighbor]--
if indegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
if len(result) != len(indegree) {
return ""
}
return string(result)
}