Alien Dictionary

Infer character order from words that are sorted in an unknown alphabet.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Alien Dictionary: Use the first difference of each adjacent word pair as a directed edge, then emit zero-indegree letters with Kahn topological sorting.

Input and goalInfer character order from words that are sorted in an unknown alphabet.

Initialize every characterCreate graph and indegree entries for w,e,r,t,f before adding edges, so isolated letters would also appear in the answer.

w0e1r2t3f4

words[wrt, wrf, er, ett, rftt]rulesnone yetindegreew:0 e:0 r:0 t:0 f:0

Recognize it

Use this pattern when sorted composite values imply a hidden ordering among symbols and only the earliest differing position can establish precedence.

Keep true

After processing each word pair, every recorded edge is a necessary character precedence; during Kahn traversal, ready contains exactly known zero-indegree un-emitted characters and emitted never violates an edge.

Reuse it

Extract only logically forced local precedence constraints, include unconstrained nodes, reject malformed prefix input, then topologically order and verify every node was emitted.

Pattern: Build character rules, then topological sort.

Simple idea: Compare each neighboring pair of words. Their first different characters give one order rule. Include characters with no edges. Reject a longer word placed before its exact prefix.

from collections import deque

def _first_difference(first: str, second: str) -> tuple[str, str] | None:
   for first_char, second_char in zip(first, second, strict=False):
      if first_char != second_char:
         return first_char, second_char
   return None


def alien_order(words: list[str]) -> str:
   graph = {char: set() for word in words for char in word}
   indegree = {char: 0 for char in graph}

   for first, second in zip(words, words[1:], strict=False):
      difference = _first_difference(first, second)
      if difference is None:
         if len(first) > len(second):
            return ""
         continue

      first_char, second_char = difference
      if second_char not in graph[first_char]:
         graph[first_char].add(second_char)
         indegree[second_char] += 1

   ready = deque(char for char, count in indegree.items() if count == 0)
   order: list[str] = []

   while ready:
      char = ready.popleft()
      order.append(char)
      for next_char in graph[char]:
         indegree[next_char] -= 1
         if indegree[next_char] == 0:
            ready.append(next_char)

   return "".join(order) if len(order) == len(indegree) else ""

Cost: $O(C+E)$ time and space, where $C$ is the total number of characters read.