GraphProblem 17 of 43
Given a sorted Dictionary of an Alien Language, find order of characters
Problem Statement
Given a sorted dictionary (array of words) of an alien language, find the order of characters in that language. The dictionary is sorted according to the alien language's rules.
Example:
- Input:
words = ["baa", "abcd", "abca", "cab", "cad"] - Output:
b d a c(b comes before a, d comes before a, a comes before c)
Noob-Friendly Explanation
Imagine aliens have their own alphabet, and they've given you their dictionary sorted in THEIR order (not a-b-c like English). By comparing adjacent words, you can figure out which alien letter comes before which.
For example, if "baa" comes before "abcd", then 'b' must come before 'a' in the alien alphabet (because we compare the first different character). By collecting all such relationships, you build a directed graph and find the order using topological sort.
Approach 1: Brute Force (DFS Topological Sort)
Intuition
Compare adjacent words to find character ordering relationships. Build a directed graph. Use DFS-based topological sort to find the order.
Algorithm
- Compare each pair of adjacent words character by character.
- The first mismatching character tells us the ordering (char in word1 comes before char in word2).
- Build a directed graph from these relationships.
- Perform DFS topological sort.
java
import java.util.*;
public class AlienDictionaryDFS {
public static String alienOrder(String[] words) {
// Build graph
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> visited = new HashMap<>(); // 0: unvisited, 1: in-stack, 2: done
// Initialize all characters
for (String word : words) {
for (char c : word.toCharArray()) {
graph.putIfAbsent(c, new HashSet<>());
visited.putIfAbsent(c, 0);
}
}
// Compare adjacent words
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());
// Edge case: if w1 is longer and is a prefix of w2, invalid
if (w1.length() > w2.length() && w1.startsWith(w2)) {
return "";
}
for (int j = 0; j < minLen; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
graph.get(w1.charAt(j)).add(w2.charAt(j));
break;
}
}
}
// DFS topological sort
StringBuilder result = new StringBuilder();
for (char c : graph.keySet()) {
if (visited.get(c) == 0) {
if (dfs(graph, visited, c, result)) {
return ""; // cycle detected
}
}
}
return result.reverse().toString();
}
static boolean dfs(Map<Character, Set<Character>> graph,
Map<Character, Integer> visited, char node, StringBuilder result) {
visited.put(node, 1); // in current path
for (char neighbor : graph.get(node)) {
if (visited.get(neighbor) == 1) return true; // cycle
if (visited.get(neighbor) == 0) {
if (dfs(graph, visited, neighbor, result)) return true;
}
}
visited.put(node, 2); // done
result.append(node);
return false;
}
public static void main(String[] args) {
String[] words = {"baa", "abcd", "abca", "cab", "cad"};
System.out.println(alienOrder(words)); // bdac
}
}Complexity Analysis
- Time Complexity: O(N × M + K) — N words with max length M for comparisons, K unique characters for topological sort.
- Space Complexity: O(K) — for the graph and visited map where K is the number of unique characters.
Approach 2: Optimal (BFS — Kahn's Algorithm)
Intuition
Build the same directed graph from word comparisons, but use BFS (Kahn's algorithm) for topological sort. This is often preferred because it naturally detects cycles (if result length < number of characters).
Algorithm
- Compare adjacent words to build the graph and in-degree map.
- Add all characters with in-degree 0 to a queue.
- BFS: process queue, reduce in-degrees, add newly zero-in-degree characters.
- If result contains all characters, return it; otherwise, there's a cycle.
java
import java.util.*;
public class AlienDictionaryBFS {
public static String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
// Initialize all characters
for (String word : words) {
for (char c : word.toCharArray()) {
graph.putIfAbsent(c, new HashSet<>());
inDegree.putIfAbsent(c, 0);
}
}
// Compare adjacent words to build edges
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.startsWith(w2)) {
return ""; // invalid ordering
}
for (int j = 0; j < minLen; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
char from = w1.charAt(j);
char to = w2.charAt(j);
if (!graph.get(from).contains(to)) {
graph.get(from).add(to);
inDegree.put(to, inDegree.get(to) + 1);
}
break;
}
}
}
// BFS topological sort
Queue<Character> queue = new LinkedList<>();
for (char c : inDegree.keySet()) {
if (inDegree.get(c) == 0) {
queue.add(c);
}
}
StringBuilder result = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
result.append(c);
for (char neighbor : graph.get(c)) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) == 0) {
queue.add(neighbor);
}
}
}
if (result.length() != inDegree.size()) {
return ""; // cycle detected
}
return result.toString();
}
public static void main(String[] args) {
String[] words = {"baa", "abcd", "abca", "cab", "cad"};
System.out.println(alienOrder(words)); // bdac
}
}Complexity Analysis
- Time Complexity: O(N × M + K) — N words, M max length for building the graph, K characters for BFS.
- Space Complexity: O(K) — for the graph, in-degree map, and queue.