Alien Dictionary
Alien Dictionary – Hard Level Problem
Foreign language uses the Latin alphabet, but its letter order differs from the standard English sequence of “a, b, c, … z.“
You’re given a list of non-empty words from the dictionary, sorted lexicographically according to the rules of this new language.
Your task is to determine the letter order in this language. If the order is invalid, return an empty string. If there are multiple valid orders, return any one of them.
Point to be noted:
String a is considered lexicographically smaller than a string b if either:
1. The first character where they differ in a is smaller than the corresponding character in b.
2. All characters in a match those in b, but a is shorter in length than b.
1. The first character where they differ in a is smaller than the corresponding character in b.
2. All characters in a match those in b, but a is shorter in length than b.
Examples related to Alien Dictionary Problem
Example 1:
Input: ["z","o"]
Output: "zo"
Explanation: From "z" and "o", we know 'z' < 'o', so return "zo".
Output: "zo"
Explanation: From "z" and "o", we know 'z' < 'o', so return "zo".
Input: ["hrn","hrf","er","enn","rfnn"]
Output: "hernf"
Explanation:
from "hrn" and "hrf", we know 'n' < 'f'
from "hrf" and "er", we know 'h' < 'e'
from "er" and "enn", we know get 'r' < 'n'
from "enn" and "rfnn" we know 'e'<'r'
so one possibile solution is "hernf"
Output: "hernf"
Explanation:
from "hrn" and "hrf", we know 'n' < 'f'
from "hrf" and "er", we know 'h' < 'e'
from "er" and "enn", we know get 'r' < 'n'
from "enn" and "rfnn" we know 'e'<'r'
so one possibile solution is "hernf"
Constraints:
- Input words will contain characters only from lowercase ‘a’ to ‘z’.
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100
Hints to solve Alien Dictionary Problem
Recommended Time & Space Complexity
Aim for a solution with O(N + V + E) time and O(V + E) space, where:
- N is the total length of all the strings.
- V is the number of unique characters (vertices).
- E is the number of edges in the graph.
Hint 1:
- Think of this problem as a graph task where each character (a to z) is a node. Edges represent dependencies between characters.
- To determine the edges, try comparing two adjacent words in the given list.
Hint 2:
Relative order between characters acts as a directed edge.
For example, in [“ape”, “apple”], ‘e’ must come before ‘p’, so there’s an edge e → p.
Build an adjacency list by comparing consecutive words and identifying these relationships.
Which algorithm can help determine a valid order?
Hint 3:
Topological Sort is a good fit for finding valid orderings. Using DFS, traverse the graph built from the adjacency list.
Maintain a visited map to track nodes in the current DFS path. A value of False means the node isn’t in the current path, while True indicates it is.
Detecting a cycle during traversal means the order is invalid.
Hint 4:
Perform a post-order traversal using DFS. When visiting a node and its children without finding a cycle, mark it as False in the visited map and append it to the result list.
If a cycle is detected, return an empty string. Otherwise, reverse the result list to get the topological order and return it.
Methods to Solve Alien Dictionary Problem
There are mainly 2 approaches to solve Alien Dictionary problem:
- Depth First Search Method
- Topological Sort (Kahn’s Algorithm)
1. Depth First Search Method
This approach builds a directed graph from the given words, where edges represent the relative order of characters. DFS is used to traverse the graph, detecting cycles and determining a valid topological order by recording nodes in post-order.
- Time complexity: O(N+V+E)
- Space complexity: O(V+E)
Where V is the number of unique characters, E is the number of edges and N is the sum of lengths of all the strings.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
unordered_map> adj;
unordered_map visited;
string result;
string foreignDictionary(vector& words) {
for (const auto& word : words) {
for (char ch : word) {
adj[ch];
}
}
for (size_t i = 0; i < words.size() - 1; ++i) {
const string& w1 = words[i], & w2 = words[i + 1];
size_t minLen = min(w1.length(), w2.length());
if (w1.length() > w2.length() &&
w1.substr(0, minLen) == w2.substr(0, minLen)) {
return "";
}
for (size_t j = 0; j < minLen; ++j) {
if (w1[j] != w2[j]) {
adj[w1[j]].insert(w2[j]);
break;
}
}
}
for (const auto& pair : adj) {
if (dfs(pair.first)) {
return "";
}
}
reverse(result.begin(), result.end());
return result;
}
bool dfs(char ch) {
if (visited.find(ch) != visited.end()) {
return visited[ch];
}
visited[ch] = true;
for (char next : adj[ch]) {
if (dfs(next)) {
return true;
}
}
visited[ch] = false;
result.push_back(ch);
return false;
}
};
Java
public class Solution {
private Map> adj;
private Map visited;
private List result;
public String foreignDictionary(String[] words) {
adj = new HashMap<>();
for (String word : words) {
for (char c : word.toCharArray()) {
adj.putIfAbsent(c, new HashSet<>());
}
}
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)) {
adj.get(w1.charAt(j)).add(w2.charAt(j));
break;
}
}
}
visited = new HashMap<>();
result = new ArrayList<>();
for (char c : adj.keySet()) {
if (dfs(c)) {
return "";
}
}
Collections.reverse(result);
StringBuilder sb = new StringBuilder();
for (char c : result) {
sb.append(c);
}
return sb.toString();
}
private boolean dfs(char ch) {
if (visited.containsKey(ch)) {
return visited.get(ch);
}
visited.put(ch, true);
for (char next : adj.get(ch)) {
if (dfs(next)) {
return true;
}
}
visited.put(ch, false);
result.add(ch);
return false;
}
}
Python
class Solution:
def foreignDictionary(self, words: List[str]) -> str:
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break
visited = {}
res = []
def dfs(char):
if char in visited:
return visited[char]
visited[char] = True
for neighChar in adj[char]:
if dfs(neighChar):
return True
visited[char] = False
res.append(char)
for char in adj:
if dfs(char):
return ""
res.reverse()
return "".join(res)
JavaScript
class Solution {
/**
* @param {string[]} words
* @returns {string}
*/
foreignDictionary(words) {
const adj = {};
for (const word of words) {
for (const char of word) {
adj[char] = new Set();
}
}
for (let i = 0; i < words.length - 1; i++) {
const w1 = words[i];
const w2 = words[i + 1];
const 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]) {
adj[w1[j]].add(w2[j]);
break;
}
}
}
const visited = {};
const res = [];
const dfs = (char) => {
if (char in visited) return visited[char];
visited[char] = true;
for (const neighChar of adj[char]) {
if (dfs(neighChar)) return true;
}
visited[char] = false;
res.push(char);
return false;
};
for (const char in adj) {
if (dfs(char)) return "";
}
res.reverse();
return res.join("");
}
}
2. Topological Sort (Kahn’s Algorithm)
This method uses an adjacency list and an in-degree array to represent the graph. It processes nodes with zero in-degree using a queue, ensuring a valid topological order. If all nodes are processed, the order is valid; otherwise, a cycle exists.
- Time complexity: O(N+V+E)
- Space complexity: O(V+E)
Where V is the number of unique characters, E is the number of edges and N is the sum of lengths of all the strings.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
string foreignDictionary(vector& words) {
unordered_map> adj;
unordered_map indegree;
for (string w : words) {
for (char c : w) {
adj[c] = unordered_set();
indegree[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]);
indegree[w2[j]]++;
}
break;
}
}
}
queue q;
for (auto &[c, deg] : indegree) {
if (deg == 0) {
q.push(c);
}
}
string res;
while (!q.empty()) {
char char_ = q.front();
q.pop();
res += char_;
for (char neighbor : adj[char_]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return res.size() == indegree.size() ? res : "";
}
};
Java
public class Solution {
public String foreignDictionary(String[] words) {
Map> adj = new HashMap<>();
Map indegree = new HashMap<>();
for (String word : words) {
for (char c : word.toCharArray()) {
adj.putIfAbsent(c, new HashSet<>());
indegree.putIfAbsent(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i];
String 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)) {
if (!adj.get(w1.charAt(j)).contains(w2.charAt(j))) {
adj.get(w1.charAt(j)).add(w2.charAt(j));
indegree.put(w2.charAt(j),
indegree.get(w2.charAt(j)) + 1);
}
break;
}
}
}
Queue q = new LinkedList<>();
for (char c : indegree.keySet()) {
if (indegree.get(c) == 0) {
q.offer(c);
}
}
StringBuilder res = new StringBuilder();
while (!q.isEmpty()) {
char char_ = q.poll();
res.append(char_);
for (char neighbor : adj.get(char_)) {
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0) {
q.offer(neighbor);
}
}
}
if (res.length() != indegree.size()) {
return "";
}
return res.toString();
}
}
Python
class Solution:
def foreignDictionary(self, words):
adj = {c: set() for w in words for c in w}
indegree = {c: 0 for c in adj}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]:
adj[w1[j]].add(w2[j])
indegree[w2[j]] += 1
break
q = deque([c for c in indegree if indegree[c] == 0])
res = []
while q:
char = q.popleft()
res.append(char)
for neighbor in adj[char]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
if len(res) != len(indegree):
return ""
return "".join(res)
JavaScript
class Solution {
/**
* @param {string[]} words
* @returns {string}
*/
foreignDictionary(words) {
let adj = {};
let indegree = {};
for (let w of words) {
for (let c of w) {
adj[c] = new Set();
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]].has(w2[j])) {
adj[w1[j]].add(w2[j]);
indegree[w2[j]] += 1;
}
break;
}
}
}
let q = new Queue();
for (let c in indegree) {
if (indegree[c] === 0) {
q.push(c);
}
}
let res = [];
while (!q.isEmpty()) {
let char = q.pop();
res.push(char);
for (let neighbor of adj[char]) {
indegree[neighbor] -= 1;
if (indegree[neighbor] === 0) {
q.push(neighbor);
}
}
}
if (res.length !== Object.keys(indegree).length) {
return "";
}
return res.join("");
}
}
