Course4all
Join us on telegram
Home/dsa/Graphs/Alien Dictionary

Alien Dictionary

Master this topic with zero to advance depth.

Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

Visual Representation

Words: ["wrt","wrf","er","ett","rftt"] Comparisons: 1. "wrt" vs "wrf" -> t comes before f (t -> f) 2. "wrf" vs "er" -> w comes before e (w -> e) 3. "er" vs "ett" -> r comes before t (r -> t) 4. "ett" vs "rftt" -> e comes before r (e -> r) Graph: w -> e -> r -> t -> f Result: "wertf"
Hard

Examples

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

From the comparisons, the order is w < e < r < t < f.

Approach 1

Level II: Intermediate (Topological Sort / DFS)

Intuition

Alternatively, you can use DFS to perform a topological sort. For each character, we explore all its 'neighbors' and then add the character to a stack.

Thought Process

  1. Graph preparation is the same as Level III.
  2. Use a state map: 0 = unvisited, 1 = visiting (checking for cycles), 2 = visited.
  3. In DFS(u):
    • If state is 1, return cycle found.
    • If state is 2, return OK.
    • Set state to 1.
    • DFS neighbors. If any fails, return false.
    • Set state to 2 and prepend u to result list.

Pattern: DFS Cycle Detection

⏱ O(C) - Where C is total characters.💾 O(1) - alphabet size fix.

Detailed Dry Run

["wrt","wrf","er"]

  • t->f, w->e
  • DFS(w): DFS(e), prepend e, prepend w. Order: we...
  • DFS(r)... final order wertf.
java
class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) adj.putIfAbsent(c, new HashSet<>());
        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)) {
                    adj.get(w1.charAt(j)).add(w2.charAt(j));
                    break;
                }
            }
        }
        Map<Character, Integer> visited = new HashMap<>(); // 0: unvisited, 1: visiting, 2: visited
        StringBuilder sb = new StringBuilder();
        for (char c : adj.keySet()) if (!dfs(c, adj, visited, sb)) return "";
        return sb.reverse().toString();
    }
    private boolean dfs(char u, Map<Character, Set<Character>> adj, Map<Character, Integer> visited, StringBuilder sb) {
        if (visited.getOrDefault(u, 0) == 1) return false;
        if (visited.getOrDefault(u, 0) == 2) return true;
        visited.put(u, 1);
        for (char v : adj.get(u)) if (!dfs(v, adj, visited, sb)) return false;
        visited.put(u, 2);
        sb.append(u);
        return true;
    }
}
Approach 2

Level III: Optimal (Topological Sort / Kahn's)

Intuition

The sorted list of words gives us relative ordering of characters. This is a classic Topological Sort problem. We extract dependencies from adjacent words and then apply Kahn's algorithm.

Thought Process

  1. Initialize a graph adj and indegree map for all unique characters.
  2. Compare every two adjacent words word1 and word2:
    • Find the first non-matching character c1 in word1 and c2 in word2.
    • Add edge c1 -> c2 and increment indegree[c2].
    • Edge case: If word2 is a prefix of word1 (e.g., "abc", "ab"), return "" (invalid).
  3. Apply Kahn's Algorithm (standard BFS topological sort).
  4. If the resulting string length != number of unique characters, a cycle exists; return "".

Pattern: Lexicographical Ordering / Kahn's

⏱ O(C) where C is the total number of characters in all words (comparison and graph building).💾 O(1) - alphabet size is fixed (26).

Detailed Dry Run

["wrt","wrf","er"]

  • t -> f, w -> e
  • Unique: {w,r,t,f,e}
  • Indegrees: f:1, e:1, others:0
  • Queue: [w, r, t]
  • Pop w: Order "w", e's indegree -> 0, Queue [r, t, e]
  • ... final order "wertf"
java
import java.util.*;

public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) indegree.put(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 (!adj.getOrDefault(w1.charAt(j), new HashSet<>()).contains(w2.charAt(j))) {
                        adj.computeIfAbsent(w1.charAt(j), k -> new HashSet<>()).add(w2.charAt(j));
                        indegree.put(w2.charAt(j), indegree.get(w2.charAt(j)) + 1);
                    }
                    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);
            if (adj.containsKey(c)) {
                for (char nbr : adj.get(c)) {
                    indegree.put(nbr, indegree.get(nbr) - 1);
                    if (indegree.get(nbr) == 0) q.add(nbr);
                }
            }
        }
        return sb.length() == indegree.size() ? sb.toString() : "";
    }
}
← Previous QuestionShortest Path in Binary Matrix
Next Question →Minimum Cost to Connect All Points