Start practising

Alien Dictionary

Hard Graphs Topological Sort Original on NeetCode

Alien Dictionary is a hard graphs problem solved with the topological sort pattern. The best approach, kahn's algorithm on letters, runs in O(C) time and O(1) space. Below are 2 approaches in Java, from dfs topological sort up.

Problem

A new alien language uses the English letters in an unknown order. You get a list of words sorted by the alien alphabet. Work out an order of the letters that is consistent with the list, or return "" if the list is contradictory.

Examples

Example 1

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

Example 2

Input
words = ["abc", "ab"]
Output
""
Why
A longer word before its own prefix is impossible in any order.

Constraints

  • 1 <= words.length <= 100; lowercase letters.
  • Return any valid order, or "" if none exists.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
DFS topological sortO(C)O(1)
Kahn's algorithm on lettersO(C)O(1)

1DFS topological sort

TimeO(C)C = total characters in all words.
SpaceO(1)At most 26 letters and 26² edges.

Build edges from adjacent word pairs, then DFS with three states over every letter that appears. A back edge means a contradiction.

  1. For each adjacent pair, add an edge at the first difference (or fail on the prefix case).
  2. DFS postorder, reverse; fail on a cycle.
Java
class Solution {
    public String foreignDictionary(String[] words) {
        boolean[][] edge = new boolean[26][26];
        boolean[] present = new boolean[26];
        for (String w : words) for (char c : w.toCharArray()) present[c - 'a'] = true;
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int j = 0;
            while (j < a.length() && j < b.length() && a.charAt(j) == b.charAt(j)) j++;
            if (j == Math.min(a.length(), b.length())) { if (a.length() > b.length()) return ""; continue; }
            edge[a.charAt(j) - 'a'][b.charAt(j) - 'a'] = true;
        }
        int[] state = new int[26];
        StringBuilder sb = new StringBuilder();
        for (int c = 0; c < 26; c++)
            if (present[c] && state[c] == 0 && !dfs(c, edge, present, state, sb)) return "";
        return sb.reverse().toString();
    }

    private boolean dfs(int u, boolean[][] edge, boolean[] present, int[] state, StringBuilder sb) {
        state[u] = 1;
        for (int v = 0; v < 26; v++) {
            if (!edge[u][v]) continue;
            if (state[v] == 1) return false;
            if (state[v] == 0 && !dfs(v, edge, present, state, sb)) return false;
        }
        state[u] = 2;
        sb.append((char) ('a' + u));
        return true;
    }
}

2Kahn's algorithm on letters

TimeO(C)
SpaceO(1)

Same edges, but compute in-degrees and repeatedly output letters with in-degree 0. If some letters are never output, there is a cycle.

  1. Build a deduplicated edge set and in-degrees for present letters.
  2. Queue letters with in-degree 0; pop into the result.
  3. Return "" if the result is shorter than the number of letters present.
Java
class Solution {
    public String foreignDictionary(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) { adj.putIfAbsent(c, new HashSet<>()); indeg.putIfAbsent(c, 0); }
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int j = 0;
            while (j < a.length() && j < b.length() && a.charAt(j) == b.charAt(j)) j++;
            if (j == Math.min(a.length(), b.length())) { if (a.length() > b.length()) return ""; continue; }
            if (adj.get(a.charAt(j)).add(b.charAt(j))) indeg.merge(b.charAt(j), 1, Integer::sum);
        }
        Queue<Character> q = new ArrayDeque<>();
        for (Map.Entry<Character, Integer> e : indeg.entrySet()) if (e.getValue() == 0) q.add(e.getKey());
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char u = q.poll();
            sb.append(u);
            for (char v : adj.get(u)) if (indeg.merge(v, -1, Integer::sum) == 0) q.add(v);
        }
        return sb.length() == indeg.size() ? sb.toString() : "";
    }
}

Edge cases to test

  • Prefix appearing after the longer word (invalid)
  • Letters that appear but have no ordering constraints
  • Contradictions forming a cycle

Hints

Hint 1

Only the first differing letter of two adjacent words tells you anything: it gives one edge a → b.

Hint 2

Then it is a topological sort over the letters.

FAQ

What is the best time complexity for Alien Dictionary?

Kahn's algorithm on letters runs in O(C) time and O(1) extra space.

Which pattern does Alien Dictionary use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Alien Dictionary?

Yes. DFS topological sort takes O(C) time and O(1) space. Build edges from adjacent word pairs, then DFS with three states over every letter that appears.

Which edge cases should I test for Alien Dictionary?

Prefix appearing after the longer word (invalid); Letters that appear but have no ordering constraints; Contradictions forming a cycle.