Alien Dictionary

Examples

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

Comparing consecutive words: wrt/wrf gives t before f, wrf/er gives w before e, er/ett gives r before t, ett/rftt gives e before r. Together these force the order w, e, r, t, f.

Input: words = ["z","x"]
Output: "zx"

The first word starts with z, the second with x, so z must come before x in this alphabet.

Input: words = ["z","x","z"]
Output: ""

z before x (from words 1-2) and x before z (from words 2-3) can't both be true, so no valid ordering exists.

Constraints

• 1 <= words.length <= 100

• 1 <= words[i].length <= 100

• words[i] consists only of lowercase English letters.

Approach

Every consecutive pair of words in the list gives one clue: scan both words left to right for the first position where their letters differ - the letter from the earlier word must come before the letter from the later word in the alien alphabet. (If no differing position is found because one word is a prefix of the other, the only valid case is the shorter word coming first; if the longer word comes first, that's an immediate contradiction, since a word can never sort before its own prefix.)

Collecting these clues from every consecutive pair builds a directed graph where an edge a -> b means "a comes before b." Any valid alphabet ordering is then just a topological sort of this graph - found either with repeated removal of in-degree-zero nodes (Kahn's algorithm) or with a DFS-based ordering that also detects cycles. If the graph has a cycle, no valid ordering exists and the answer is an empty string. Any letters that appear in the words but never get an edge still need to appear somewhere in the output.

Solutions

Build Graph + Kahn's Algorithm (BFS Topological Sort)

First collect every letter that appears anywhere in the word list, and build a directed graph (adjacency list plus in-degree counts) from the ordering clues found between each pair of consecutive words. Then run Kahn's algorithm: start a queue with every letter that has in-degree zero (no letter is known to come before it), repeatedly pop a letter, append it to the result, and decrement the in-degree of everything it points to, adding any letter whose in-degree drops to zero. If the final result doesn't include every letter, the graph had a cycle (or an unresolved tie), so return an empty string.

function alienOrder(words) {
  const allLetters = new Set();
  for (const word of words) {
    for (const ch of word) allLetters.add(ch);
  }

  const graph = new Map();
  const inDegree = new Map();
  for (const ch of allLetters) {
    graph.set(ch, new Set());
    inDegree.set(ch, 0);
  }

  for (let i = 0; i < words.length - 1; i++) {
    const first = words[i];
    const second = words[i + 1];
    const minLen = Math.min(first.length, second.length);

    let foundDifference = false;
    for (let j = 0; j < minLen; j++) {
      if (first[j] !== second[j]) {
        if (!graph.get(first[j]).has(second[j])) {
          graph.get(first[j]).add(second[j]);
          inDegree.set(second[j], inDegree.get(second[j]) + 1);
        }
        foundDifference = true;
        break;
      }
    }

    // "abc" before "ab" can never be valid - a word can't sort before its own prefix.
    if (!foundDifference && first.length > second.length) {
      return "";
    }
  }

  const queue = [];
  for (const ch of allLetters) {
    if (inDegree.get(ch) === 0) queue.push(ch);
  }

  const order = [];
  while (queue.length > 0) {
    const ch = queue.shift();
    order.push(ch);
    for (const next of graph.get(ch)) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) queue.push(next);
    }
  }

  return order.length === allLetters.size ? order.join("") : "";
}

Time: O(C) where C is the total number of characters across all words, since building the graph scans each word once and the topological sort visits every letter and edge once · Space: O(1) for the graph and in-degree map, since there are at most 26 letters, plus O(C) used while scanning the words

DFS-Based Topological Sort with Cycle Detection

Build the same directed graph of ordering clues. Then run a DFS from every letter, tracking each letter's state as unvisited, currently on the active path (visiting), or fully processed (visited). After fully exploring all of a letter's outgoing edges, append that letter to the result - so letters that depend on nothing further get appended first. If the DFS ever reaches a letter that is currently visiting (still on the active path), that's a cycle, so return an empty string. Reversing the final append order gives a valid topological ordering.

function alienOrder(words) {
  const allLetters = new Set();
  for (const word of words) {
    for (const ch of word) allLetters.add(ch);
  }

  const graph = new Map();
  for (const ch of allLetters) graph.set(ch, new Set());

  for (let i = 0; i < words.length - 1; i++) {
    const first = words[i];
    const second = words[i + 1];
    const minLen = Math.min(first.length, second.length);

    let foundDifference = false;
    for (let j = 0; j < minLen; j++) {
      if (first[j] !== second[j]) {
        graph.get(first[j]).add(second[j]);
        foundDifference = true;
        break;
      }
    }
    if (!foundDifference && first.length > second.length) {
      return "";
    }
  }

  const state = new Map(); // "visiting" | "visited"
  const order = [];
  let hasCycle = false;

  function dfs(ch) {
    if (hasCycle) return;
    if (state.get(ch) === "visiting") {
      hasCycle = true;
      return;
    }
    if (state.get(ch) === "visited") return;

    state.set(ch, "visiting");
    for (const next of graph.get(ch)) {
      dfs(next);
    }
    state.set(ch, "visited");
    order.push(ch);
  }

  for (const ch of allLetters) {
    if (state.get(ch) === undefined) dfs(ch);
  }

  if (hasCycle) return "";
  return order.reverse().join("");
}

Time: O(C) where C is the total number of characters across all words, for the same reasons as the BFS version · Space: O(1) for the graph and state map, since there are at most 26 letters, plus O(C) used while scanning the words