loading

Alien Dictionary — Step-by-Step Visualization

hardLeetCode #269GraphTopological SortString

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. Derive the order of letters in this language. If the given words are invalid (e.g., a cycle exists), return an empty string.

Algorithm Pattern

Topological Sort (Kahn's Algorithm)

Key Idea

Since the words are sorted lexicographically, comparing adjacent words gives us priority rules between characters. For example, if 'wrt' comes before 'wrf', then 't' must come before 'f'. These rules form a directed acyclic graph (DAG). A topological sort of this graph gives the correct character order. If the graph has a cycle, the words are invalid.

Step-by-Step Approach

  1. Find all unique characters in `words`.
  2. Build a directed graph `adj` and an `inDegree` map by comparing adjacent words.
  3. Identify the first differing character in words `w1` and `w2` to add an edge `w1[j] -> w2[j]`.
  4. Use a queue to process characters with `inDegree == 0` (topological sort).
  5. If the result length matches the total unique characters, return the order. Else, return '' (cycle).

Common Gotchas

  • Handle the 'prefix' case: if word1 is a prefix of word2 but comes after it (e.g., ['abc', 'ab']), it's invalid.
  • Ensure characters with no dependencies (isolated nodes) are included in the final order.

Related Problems

← All problems