Alien Dictionary
Part of Practice: Hard Path Structures
An alien language uses lowercase English letters, but in an unknown alphabetical order. You are given a list of words claimed to be sorted according to that unknown order. Reconstruct and return any letter ordering consistent with the list, using only letters that appear in the words. If the list is self-contradictory — the letter comparisons form a cycle, or a longer word appears before its own prefix — return the empty string.
Constraints that matter: at most 100 words of length up to 100, so efficiency is easy; the challenge is extracting the right constraints and handling the invalid cases.
Examples
- Input:
- words = ["wrt","wrf","er","ett","rftt"]
- Output:
- "wertf"
wrt vs wrf gives t before f; wrf vs er gives w before e; er vs ett gives r before t; ett vs rftt gives e before r. Chaining these: w, e, r, t, f.
- Input:
- words = ["z","x"]
- Output:
- "zx"
- Input:
- words = ["z","x","z"]
- Output:
- ""
The first pair says z comes before x, the second says x comes before z — a contradiction.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.