Alien Dictionary

hard graph topological sort

Problem

You are given a list of words from an alien language, already sorted by that language's unknown lexicographic order. Recover one valid ordering of the alphabet, or return "" if none exists.

Compare each adjacent pair of words. The first differing pair of characters (a, b) gives an edge a → b meaning "a comes before b". After collecting every edge, do a topological sort (Kahn's algorithm). If a cycle blocks completion, no valid order exists.

Inputwords = ["wrt","wrf","er","ett","rftt"]

Output"wertf"

words (comma-separated)

from collections import deque, defaultdict

def alien_order(words):
    indeg = {c: 0 for w in words for c in w}
    graph = defaultdict(set)
    for w1, w2 in zip(words, words[:-1] + [None][1:] + words[1:]):
        if w2 is None: break
        if len(w1) > len(w2) and w1.startswith(w2):
            return ""
        for a, b in zip(w1, w2):
            if a != b:
                if b not in graph[a]:
                    graph[a].add(b)
                    indeg[b] += 1
                break
    q = deque(c for c in indeg if indeg[c] == 0)
    out = []
    while q:
        c = q.popleft()
        out.append(c)
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return "".join(out) if len(out) == len(indeg) else ""

function alienOrder(words) {
  const indeg = new Map();
  const graph = new Map();
  for (const w of words) for (const c of w) { if (!indeg.has(c)) { indeg.set(c, 0); graph.set(c, new Set()); } }
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    if (w1.length > w2.length && w1.startsWith(w2)) return "";
    for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
      if (w1[j] !== w2[j]) {
        if (!graph.get(w1[j]).has(w2[j])) {
          graph.get(w1[j]).add(w2[j]);
          indeg.set(w2[j], indeg.get(w2[j]) + 1);
        }
        break;
      }
    }
  }
  const q = [];
  for (const [c, d] of indeg) if (d === 0) q.push(c);
  const out = [];
  while (q.length) {
    const c = q.shift();
    out.push(c);
    for (const nxt of graph.get(c)) {
      indeg.set(nxt, indeg.get(nxt) - 1);
      if (indeg.get(nxt) === 0) q.push(nxt);
    }
  }
  return out.length === indeg.size ? out.join("") : "";
}

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Integer> indeg = new HashMap<>();
        Map<Character, Set<Character>> graph = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) {
            indeg.putIfAbsent(c, 0);
            graph.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 "";
            int n = Math.min(w1.length(), w2.length());
            for (int j = 0; j < n; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (graph.get(w1.charAt(j)).add(w2.charAt(j)))
                        indeg.merge(w2.charAt(j), 1, Integer::sum);
                    break;
                }
            }
        }
        Deque<Character> q = new ArrayDeque<>();
        for (var e : indeg.entrySet()) if (e.getValue() == 0) q.add(e.getKey());
        StringBuilder out = new StringBuilder();
        while (!q.isEmpty()) {
            char c = q.poll();
            out.append(c);
            for (char nxt : graph.get(c)) {
                indeg.merge(nxt, -1, Integer::sum);
                if (indeg.get(nxt) == 0) q.add(nxt);
            }
        }
        return out.length() == indeg.size() ? out.toString() : "";
    }
}

string alienOrder(vector<string>& words) {
    unordered_map<char, int> indeg;
    unordered_map<char, set<char>> graph;
    for (auto& w : words) for (char c : w) { indeg[c]; graph[c]; }
    for (int i = 0; i + 1 < (int)words.size(); i++) {
        auto& w1 = words[i]; auto& w2 = words[i + 1];
        if (w1.size() > w2.size() && w1.substr(0, w2.size()) == w2) return "";
        int n = min(w1.size(), w2.size());
        for (int j = 0; j < n; j++) {
            if (w1[j] != w2[j]) {
                if (graph[w1[j]].insert(w2[j]).second) indeg[w2[j]]++;
                break;
            }
        }
    }
    queue<char> q;
    for (auto& [c, d] : indeg) if (d == 0) q.push(c);
    string out;
    while (!q.empty()) {
        char c = q.front(); q.pop();
        out.push_back(c);
        for (char nxt : graph[c]) {
            if (--indeg[nxt] == 0) q.push(nxt);
        }
    }
    return out.size() == indeg.size() ? out : "";
}

Explanation

The words are already sorted by the alien alphabet, so the ordering is hidden in how adjacent words differ. The clever idea is to turn those clues into a graph and then put the letters in a valid order with a topological sort.

For each pair of neighbouring words, scan until the first position where their characters differ. If word1 has a and word2 has b there, then a must come before b, so we add a directed edge a → b and increase b's in-degree. (One edge per pair — the first difference decides everything.)

Then we run Kahn's algorithm: start a queue with every letter that has in-degree 0 (nothing must come before it), pop letters one by one into the answer, and each time decrease the in-degree of their successors, enqueuing any that drop to 0.

If we manage to output every letter, that order is valid. If some letters never reach in-degree 0, there is a cycle and no order exists, so we return "". Example: from ["wrt","wrf","er","ett","rftt"] the edges give one valid answer "wertf".

Time: O(N + Σ|w|) Space: O(1) (26-char alphabet)