DSA Tracker

Visualize

Alien Dictionary

Derive edges from adjacent words, then Kahn's topological sort

time O(C)space O(1)

A sorted dictionary hides its alphabet in the FIRST letter where two neighbouring words diverge — every letter before that point already matched, so it says nothing, and one word being a prefix of the other says nothing either (unless the longer one comes first, which is impossible in any alphabet). Each divergence is one directed edge, letter before -> letter after, and once every adjacent pair has been compared, recovering the full order is exactly Kahn's topological sort: repeatedly take a letter nothing points into, and removing it may free the letters it pointed to. A cycle in these edges — like z before x and x before z — means no alphabet could produce this dictionary, and the letter count coming up short of the full order is how that shows up.

Details

Animated on: words = ["wrt", "wrf", "er", "ett", "rftt"], sorted lexicographically by an unknown alien alphabet — derive that alphabet's letter order, or "" if the words are inconsistent with any order.

Problem:Alien DictionaryHard

Derive edges from adjacent words, then Kahn's topological sort

step 1 / 14

5 words, given already sorted by this alien alphabet's rules: "wrt", "wrf", "er", "ett", "rftt". The only place two neighbouring words reveal a rule is the FIRST letter where they differ — everything before that point is already equal, and everything after is irrelevant to the comparison.

Pseudocode
1FUNCTION alienOrder(words):
2  SEED indeg[c] <- 0 FOR EVERY CHARACTER IN words
3  FOR EACH adjacent pair (w1, w2) IN words
4    IF w1 IS PREFIX OF w2 AND LENGTH(w1) > LENGTH(w2)
5      RETURN ""
6    j <- FIRST INDEX WHERE w1[j] != w2[j]
7    IF j EXISTS, ADD EDGE w1[j] -> w2[j] AND indeg[w2[j]] <- indeg[w2[j]] + 1
8  queue <- ALL c WITH indeg[c] = 0
9  WHILE queue NOT EMPTY
10    c <- REMOVE FRONT OF queue
11    APPEND c TO order
12    FOR EACH d IN next[c]
13      indeg[d] <- indeg[d] - 1
14      IF indeg[d] = 0, APPEND d TO queue
15  RETURN order IF LENGTH(order) = UNIQUE CHAR COUNT ELSE ""

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. 5 words, given already sorted by this alien alphabet's rules: "wrt", "wrf", "er", "ett", "rftt". The only place two neighbouring words reveal a rule is the FIRST letter where they differ — everything before that point is already equal, and everything after is irrelevant to the comparison.
  2. 5 distinct letters show up across the words: e, f, r, t, w. Every one starts at indegree 0 — a letter with no proven "comes after" constraint yet.
  3. "wrt" vs "wrf": they first disagree at position 2, "t" against "f", so "t" must come before "f" — a new edge t -> f, pushing f's indegree to 1.
  4. "wrf" vs "er": they first disagree at position 0, "w" against "e", so "w" must come before "e" — a new edge w -> e, pushing e's indegree to 1.
  5. "er" vs "ett": they first disagree at position 1, "r" against "t", so "r" must come before "t" — a new edge r -> t, pushing t's indegree to 1.
  6. "ett" vs "rftt": they first disagree at position 0, "e" against "r", so "e" must come before "r" — a new edge e -> r, pushing r's indegree to 1.
  7. Every adjacent pair has been compared. 4 rules survive as directed edges, and each letter's badge is how many of them still point INTO it — exactly the setup for Kahn's algorithm.
  8. Only "w" sits at indegree 0, so it is the one letter nothing is waiting on. Queue it.
  9. Take "w" — position 1 of 5 in the order. That satisfies a rule for "e": "e" now needs 0. "e" reached 0 and joins the queue.
  10. Take "e" — position 2 of 5 in the order. That satisfies a rule for "r": "r" now needs 0. "r" reached 0 and joins the queue.
  11. Take "r" — position 3 of 5 in the order. That satisfies a rule for "t": "t" now needs 0. "t" reached 0 and joins the queue.
  12. Take "t" — position 4 of 5 in the order. That satisfies a rule for "f": "f" now needs 0. "f" reached 0 and joins the queue.
  13. Take "f" — position 5 of 5 in the order. "f" has no outgoing rule left to satisfy — it never unlocks another letter.
  14. The queue emptied after all 5 letters came out of it, so the order is valid: "wertf". Had any letters been left stuck above indegree 0, they would have formed a cycle and the answer would be "".

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Alien Dictionary in the editorAll Graph problemsBack to roadmap