LeetCode 269 Alien Dictionary - Example and Complexity Analysis

Trace ["wrt","wrf","er","ett","rftt"].

Compare adjacent pairs:

• "wrt" vs "wrf": differ at index 2. 't' < 'f'.
• "wrf" vs "er": differ at index 0. 'w' < 'e'.
• "er" vs "ett": differ at index 1. 'r' < 't'.
• "ett" vs "rftt": differ at index 0. 'e' < 'r'.

Graph edges: t→f, w→e, r→t, e→r.

In-degrees: w:0, e:1, r:1, t:1, f:1.

Topological sort starting with 'w': w → e → r → t → f.

Result: "wertf".

$O(C)$ where $C$ is total characters across all words. Building graph and toposort both linear in unique characters and edges.