Alien Dictionary

Share

Given sorted list of words in an alien language, find the order of characters.

Example 1
Input: words=["wrt","wrf","er","ett","rftt"] → Output: "wertf"
Example 2
Input: words=["z","x"] → Output: "zx"

Solution Approach

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
Java
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)