Given sorted list of words in an alien language, find the order of characters.
Input: words=["wrt","wrf","er","ett","rftt"] → Output: "wertf"
Input: words=["z","x"] → Output: "zx"
Topological sort: compare adjacent words to build edges. BFS/Kahn's algorithm.
- Compare adjacent words to find ordering constraints
- Build directed graph of char dependencies
- Use Kahn's BFS topological sort
- If cycle detected return ""
- Return topological order
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
for (String w : words) for (char c : w.toCharArray()) { graph.putIfAbsent(c, new HashSet<>()); inDegree.putIfAbsent(c, 0); }
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i], w2 = words[i+1];
if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
if (w1.charAt(j) != w2.charAt(j)) {
if (graph.get(w1.charAt(j)).add(w2.charAt(j)))
inDegree.merge(w2.charAt(j), 1, Integer::sum);
break;
}
}
}
Queue<Character> q = new LinkedList<>();
for (char c : inDegree.keySet()) if (inDegree.get(c) == 0) q.add(c);
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
char c = q.poll(); sb.append(c);
for (char next : graph.get(c)) { inDegree.merge(next, -1, Integer::sum); if (inDegree.get(next) == 0) q.add(next); }
}
return sb.length() == inDegree.size() ? sb.toString() : "";
}
- Time Complexity: O(V+E)
- Space Complexity: O(V+E)