The Alien Dictionary problem gives you a list of words sorted lexicographically according to the rules of an unknown alien language. Each word is a string of lowercase English letters, but the letter order is unknown. Your task is to determine a possible order of the letters in this alien language that is consistent with the given sorted list.
words, where each string represents a word in the alien language."".Key Constraints:
words.words in a valid order, or "" if impossible.
To deduce the letter order, we need to compare adjacent words and find the first position where they differ. The differing characters reveal the relative order between those two letters. For example, if "wrt" comes before "wrf", then 't' must come before 'f' in the alien alphabet.
At first glance, one might consider brute-forcing all possible letter orders and checking which one matches the given word list. However, this is highly inefficient as there are 26! possible orders (for 26 letters). Instead, we can model the problem as finding a valid topological ordering of letters based on the "comes before" relationships we extract from the word list.
This leads us to use a graph-based approach: treat each letter as a node, and draw a directed edge from letter A to letter B if A must come before B. Then, perform a topological sort to find a valid order.
Let's break down the solution step by step:
words."abc" before "ab"), this is invalid—return ""."" as there is no valid order."".We use a hash map (dictionary) to store adjacency lists for each letter, and another hash map to track in-degrees. This allows O(1) lookups and efficient updates.
Let's use the input ["wrt", "wrf", "er", "ett", "rftt"] as an example.
Brute-force Approach: Trying all possible permutations of letters is O(N!), which is infeasible for large alphabets.
Optimized Approach:
The Alien Dictionary problem is a classic use case for topological sorting in directed graphs. By extracting ordering constraints from adjacent words, we build a graph representing letter dependencies. Topological sorting then gives us a valid letter order, or detects if no such order exists. This approach is efficient, elegant, and leverages core graph algorithms to solve a seemingly complex language problem.
from collections import defaultdict, deque
class Solution:
def alienOrder(self, words):
# Build the graph
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
# Topological sort (Kahn's algorithm)
queue = deque([c for c in in_degree if in_degree[c] == 0])
res = []
while queue:
c = queue.popleft()
res.append(c)
for nei in adj[c]:
in_degree[nei] -= 1
if in_degree[nei] == 0:
queue.append(nei)
if len(res) != len(in_degree):
return ""
return "".join(res)
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> adj;
unordered_map<char, int> in_degree;
for (const string& word : words)
for (char c : word)
in_degree[c] = 0;
for (int i = 0; i < words.size() - 1; ++i) {
string w1 = words[i], 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 (!adj[w1[j]].count(w2[j])) {
adj[w1[j]].insert(w2[j]);
in_degree[w2[j]]++;
}
break;
}
}
}
queue<char> q;
for (auto& p : in_degree)
if (p.second == 0)
q.push(p.first);
string res;
while (!q.empty()) {
char c = q.front(); q.pop();
res += c;
for (char nei : adj[c]) {
in_degree[nei]--;
if (in_degree[nei] == 0)
q.push(nei);
}
}
if (res.size() != in_degree.size()) return "";
return res;
}
};
import java.util.*;
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> adj = 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)) {
Set<Character> set = adj.getOrDefault(w1.charAt(j), new HashSet<>());
if (!set.contains(w2.charAt(j))) {
set.add(w2.charAt(j));
adj.put(w1.charAt(j), set);
inDegree.put(w2.charAt(j), inDegree.get(w2.charAt(j)) + 1);
}
break;
}
}
}
Queue<Character> queue = new LinkedList<>();
for (char c : inDegree.keySet())
if (inDegree.get(c) == 0)
queue.offer(c);
StringBuilder res = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
res.append(c);
if (adj.containsKey(c)) {
for (char nei : adj.get(c)) {
inDegree.put(nei, inDegree.get(nei) - 1);
if (inDegree.get(nei) == 0)
queue.offer(nei);
}
}
}
if (res.length() != inDegree.size()) return "";
return res.toString();
}
}
var alienOrder = function(words) {
let adj = {};
let inDegree = {};
for (let word of words)
for (let c of word)
inDegree[c] = 0;
for (let i = 0; i < words.length - 1; ++i) {
let w1 = words[i], w2 = words[i+1];
let minLen = Math.min(w1.length, w2.length);
if (w1.length > w2.length && w1.slice(0, minLen) === w2.slice(0, minLen))
return "";
for (let j = 0; j < minLen; ++j) {
if (w1[j] !== w2[j]) {
if (!adj[w1[j]]) adj[w1[j]] = new Set();
if (!adj[w1[j]].has(w2[j])) {
adj[w1[j]].add(w2[j]);
inDegree[w2[j]]++;
}
break;
}
}
}
let queue = [];
for (let c in inDegree)
if (inDegree[c] === 0)
queue.push(c);
let res = "";
while (queue.length) {
let c = queue.shift();
res += c;
if (adj[c]) {
for (let nei of adj[c]) {
inDegree[nei]--;
if (inDegree[nei] === 0)
queue.push(nei);
}
}
}
if (res.length !== Object.keys(inDegree).length) return "";
return res;
};