Alien Dictionary
HardCompare adjacent words for one ordering fact
Problem
Given words sorted in an alien language, deduce a valid order of its letters.
Each adjacent pair reveals one ordering rule; topologically sort the letters to get the alphabet.
The idea
Each adjacent pair of words yields exactly one constraint: at the first position where they differ, the earlier word's letter precedes the other's. Topologically sorting those constraints gives a valid alphabet.
The trick
- Only the first differing character tells you anything.
- A longer word before its own prefix is invalid input.
- A cycle means no consistent order exists.
Step 1 of 6. Kahn's algorithm: repeatedly take a course with 0 remaining prerequisites. indegrees [0,1,2,1].
Cycle ⇒ impossible.
1q = every course whose indegree is 02while q not empty:3 c = q.pop(); processed += 14 for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCoursesInput
- nodes
- 4, 4 edges
Memory
- indegrees
- [0,1,2,1]
- processed
- —
Output
- finish
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- words = ["baa","abcd","abca","cab","cad"]
- Output:
- "bdac"
- Explanation:
- Deduce the letter order from adjacent words.
Example 2
- Input:
- words = ["caa","aaa","aab"]
- Output:
- "cab"
- Explanation:
- Order works out to c,a,b.
Example 3
- Input:
- words = ["z","x"]
- Output:
- "zx"
- Explanation:
- z comes before x.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.