Alien Dictionary
Alien Dictionary is a hard graphs problem solved with the topological sort pattern.
The best approach, kahn's algorithm on letters, runs in O(C) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs topological sort up.
Problem
A new alien language uses the English letters in an unknown order. You get a list of words sorted by the alien alphabet. Work out an order of the letters that is consistent with the list, or return "" if the list is contradictory.
Examples
Example 1
- Input
words = ["wrt", "wrf", "er", "ett", "rftt"]- Output
"wertf"
Example 2
- Input
words = ["abc", "ab"]- Output
""- Why
- A longer word before its own prefix is impossible in any order.
Constraints
1 <= words.length <= 100; lowercase letters.- Return any valid order, or "" if none exists.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| DFS topological sort | O(C) | O(1) |
| Kahn's algorithm on letters | O(C) | O(1) |
1DFS topological sort
O(C)C = total characters in all words.O(1)At most 26 letters and 26² edges.Build edges from adjacent word pairs, then DFS with three states over every letter that appears. A back edge means a contradiction.
- For each adjacent pair, add an edge at the first difference (or fail on the prefix case).
- DFS postorder, reverse; fail on a cycle.
class Solution {
public String foreignDictionary(String[] words) {
boolean[][] edge = new boolean[26][26];
boolean[] present = new boolean[26];
for (String w : words) for (char c : w.toCharArray()) present[c - 'a'] = true;
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
int j = 0;
while (j < a.length() && j < b.length() && a.charAt(j) == b.charAt(j)) j++;
if (j == Math.min(a.length(), b.length())) { if (a.length() > b.length()) return ""; continue; }
edge[a.charAt(j) - 'a'][b.charAt(j) - 'a'] = true;
}
int[] state = new int[26];
StringBuilder sb = new StringBuilder();
for (int c = 0; c < 26; c++)
if (present[c] && state[c] == 0 && !dfs(c, edge, present, state, sb)) return "";
return sb.reverse().toString();
}
private boolean dfs(int u, boolean[][] edge, boolean[] present, int[] state, StringBuilder sb) {
state[u] = 1;
for (int v = 0; v < 26; v++) {
if (!edge[u][v]) continue;
if (state[v] == 1) return false;
if (state[v] == 0 && !dfs(v, edge, present, state, sb)) return false;
}
state[u] = 2;
sb.append((char) ('a' + u));
return true;
}
}class Solution:
def foreignDictionary(self, words: List[str]) -> str:
edge = [[False] * 26 for _ in range(26)]
present = [False] * 26
for w in words:
for c in w:
present[ord(c) - ord('a')] = True
for i in range(len(words) - 1):
a, b = words[i], words[i + 1]
j = 0
while j < len(a) and j < len(b) and a[j] == b[j]:
j += 1
if j == min(len(a), len(b)):
if len(a) > len(b):
return ""
continue
edge[ord(a[j]) - ord('a')][ord(b[j]) - ord('a')] = True
state = [0] * 26
sb = []
for c in range(26):
if present[c] and state[c] == 0 and not self.dfs(c, edge, present, state, sb):
return ""
return "".join(reversed(sb))
def dfs(self, u: int, edge: List[List[bool]], present: List[bool], state: List[int], sb: List[str]) -> bool:
state[u] = 1
for v in range(26):
if not edge[u][v]:
continue
if state[v] == 1:
return False
if state[v] == 0 and not self.dfs(v, edge, present, state, sb):
return False
state[u] = 2
sb.append(chr(ord('a') + u))
return Trueclass Solution {
public:
string foreignDictionary(vector<string>& words) {
vector<vector<bool>> edge(26, vector<bool>(26, false));
vector<bool> present(26, false);
for (const string& w : words) for (char c : w) present[c - 'a'] = true;
for (int i = 0; i + 1 < (int)words.size(); i++) {
const string& a = words[i];
const string& b = words[i + 1];
int j = 0;
while (j < (int)a.size() && j < (int)b.size() && a[j] == b[j]) j++;
if (j == (int)min(a.size(), b.size())) { if (a.size() > b.size()) return ""; continue; }
edge[a[j] - 'a'][b[j] - 'a'] = true;
}
vector<int> state(26, 0);
string sb;
for (int c = 0; c < 26; c++)
if (present[c] && state[c] == 0 && !dfs(c, edge, present, state, sb)) return "";
reverse(sb.begin(), sb.end());
return sb;
}
private:
bool dfs(int u, vector<vector<bool>>& edge, vector<bool>& present, vector<int>& state, string& sb) {
state[u] = 1;
for (int v = 0; v < 26; v++) {
if (!edge[u][v]) continue;
if (state[v] == 1) return false;
if (state[v] == 0 && !dfs(v, edge, present, state, sb)) return false;
}
state[u] = 2;
sb.push_back((char)('a' + u));
return true;
}
};function foreignDictionary(words) {
const edge = Array.from({ length: 26 }, () => new Array(26).fill(false));
const present = new Array(26).fill(false);
for (const w of words) for (let k = 0; k < w.length; k++) present[w.charCodeAt(k) - 97] = true;
for (let i = 0; i + 1 < words.length; i++) {
const a = words[i], b = words[i + 1];
let j = 0;
while (j < a.length && j < b.length && a[j] === b[j]) j++;
if (j === Math.min(a.length, b.length)) { if (a.length > b.length) return ""; continue; }
edge[a.charCodeAt(j) - 97][b.charCodeAt(j) - 97] = true;
}
const state = new Array(26).fill(0);
const sb = [];
function dfs(u) {
state[u] = 1;
for (let v = 0; v < 26; v++) {
if (!edge[u][v]) continue;
if (state[v] === 1) return false;
if (state[v] === 0 && !dfs(v)) return false;
}
state[u] = 2;
sb.push(String.fromCharCode(97 + u));
return true;
}
for (let c = 0; c < 26; c++)
if (present[c] && state[c] === 0 && !dfs(c)) return "";
return sb.reverse().join("");
}2Kahn's algorithm on letters
O(C)O(1)Same edges, but compute in-degrees and repeatedly output letters with in-degree 0. If some letters are never output, there is a cycle.
- Build a deduplicated edge set and in-degrees for present letters.
- Queue letters with in-degree 0; pop into the result.
- Return "" if the result is shorter than the number of letters present.
class Solution {
public String foreignDictionary(String[] words) {
Map<Character, Set<Character>> adj = new HashMap<>();
Map<Character, Integer> indeg = new HashMap<>();
for (String w : words) for (char c : w.toCharArray()) { adj.putIfAbsent(c, new HashSet<>()); indeg.putIfAbsent(c, 0); }
for (int i = 0; i + 1 < words.length; i++) {
String a = words[i], b = words[i + 1];
int j = 0;
while (j < a.length() && j < b.length() && a.charAt(j) == b.charAt(j)) j++;
if (j == Math.min(a.length(), b.length())) { if (a.length() > b.length()) return ""; continue; }
if (adj.get(a.charAt(j)).add(b.charAt(j))) indeg.merge(b.charAt(j), 1, Integer::sum);
}
Queue<Character> q = new ArrayDeque<>();
for (Map.Entry<Character, Integer> e : indeg.entrySet()) if (e.getValue() == 0) q.add(e.getKey());
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
char u = q.poll();
sb.append(u);
for (char v : adj.get(u)) if (indeg.merge(v, -1, Integer::sum) == 0) q.add(v);
}
return sb.length() == indeg.size() ? sb.toString() : "";
}
}class Solution:
def foreignDictionary(self, words: List[str]) -> str:
adj = {}
indeg = {}
for w in words:
for c in w:
adj.setdefault(c, set())
indeg.setdefault(c, 0)
for i in range(len(words) - 1):
a, b = words[i], words[i + 1]
j = 0
while j < len(a) and j < len(b) and a[j] == b[j]:
j += 1
if j == min(len(a), len(b)):
if len(a) > len(b):
return ""
continue
if b[j] not in adj[a[j]]:
adj[a[j]].add(b[j])
indeg[b[j]] += 1
q = deque(c for c, d in indeg.items() if d == 0)
sb = []
while q:
u = q.popleft()
sb.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return "".join(sb) if len(sb) == len(indeg) else ""class Solution {
public:
string foreignDictionary(vector<string>& words) {
unordered_map<char, unordered_set<char>> adj;
unordered_map<char, int> indeg;
for (const string& w : words) for (char c : w) { adj[c]; indeg[c]; }
for (int i = 0; i + 1 < (int)words.size(); i++) {
const string& a = words[i];
const string& b = words[i + 1];
int j = 0;
while (j < (int)a.size() && j < (int)b.size() && a[j] == b[j]) j++;
if (j == (int)min(a.size(), b.size())) { if (a.size() > b.size()) return ""; continue; }
if (adj[a[j]].insert(b[j]).second) indeg[b[j]]++;
}
queue<char> q;
for (auto& e : indeg) if (e.second == 0) q.push(e.first);
string sb;
while (!q.empty()) {
char u = q.front(); q.pop();
sb.push_back(u);
for (char v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
return sb.size() == indeg.size() ? sb : "";
}
};function foreignDictionary(words) {
const adj = new Map();
const indeg = new Map();
for (const w of words) for (const c of w) {
if (!adj.has(c)) adj.set(c, new Set());
if (!indeg.has(c)) indeg.set(c, 0);
}
for (let i = 0; i + 1 < words.length; i++) {
const a = words[i], b = words[i + 1];
let j = 0;
while (j < a.length && j < b.length && a[j] === b[j]) j++;
if (j === Math.min(a.length, b.length)) { if (a.length > b.length) return ""; continue; }
const set = adj.get(a[j]);
if (!set.has(b[j])) { set.add(b[j]); indeg.set(b[j], indeg.get(b[j]) + 1); }
}
const q = [];
for (const [c, d] of indeg) if (d === 0) q.push(c);
let sb = "";
let head = 0;
while (head < q.length) {
const u = q[head++];
sb += u;
for (const v of adj.get(u)) {
indeg.set(v, indeg.get(v) - 1);
if (indeg.get(v) === 0) q.push(v);
}
}
return sb.length === indeg.size ? sb : "";
}Edge cases to test
- Prefix appearing after the longer word (invalid)
- Letters that appear but have no ordering constraints
- Contradictions forming a cycle
Hints
Hint 1
Only the first differing letter of two adjacent words tells you anything: it gives one edge a → b.
Hint 2
Then it is a topological sort over the letters.
FAQ
What is the best time complexity for Alien Dictionary?
Kahn's algorithm on letters runs in O(C) time and O(1) extra space.
Which pattern does Alien Dictionary use?
It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.
Is there a brute force solution for Alien Dictionary?
Yes. DFS topological sort takes O(C) time and O(1) space. Build edges from adjacent word pairs, then DFS with three states over every letter that appears.
Which edge cases should I test for Alien Dictionary?
Prefix appearing after the longer word (invalid); Letters that appear but have no ordering constraints; Contradictions forming a cycle.