The problem
An alien language uses lowercase English letters in an unknown order. You are given its words sorted in dictionary order by that alphabet.
Return a string of all the letters used, in an order consistent with the sorting. Any consistent order will do; if none exists, return "".
Examples
- Input
words = ["wrt", "wrf", "er", "ett", "rftt"]
- Output
"wertf"
- Input
words = ["z", "x"]
- Output
"zx"
- Input
words = ["z", "x", "z"]
- Output
""
Constraints
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 100
- Only lowercase English letters.
The idea
Only neighbouring words tell anything, and only at their first difference: wrt before wrf says t comes before f, nothing more. One case says the list is impossible: a word before its own prefix, like abc before ab.
Each rule is an arrow between two letters, so the alphabet is a topological order of those arrows — found with Kahn’s algorithm, as in Course Schedule II. If some letters never become free, the rules contain a cycle and no alphabet exists.
- Time
- O(C) — C the total letters in all words
- Space
- O(U + R) — U letters, R rules, both at most 26 and 26²
Solution · every language run against every case
class Solution: def alienOrder(self, words: List[str]) -> str: letters = {c for w in words for c in w} after = {c: set() for c in letters} # letter -> letters known to come after it need = {c: 0 for c in letters} # letter -> how many letters must come before it for a, b in zip(words, words[1:]): for x, y in zip(a, b): if x != y: # the first difference is the only thing this pair tells us if y not in after[x]: after[x].add(y) need[y] += 1 break else: if len(a) > len(b): return "" # "abc" before "ab" cannot be sorted in any alphabet # Kahn's algorithm, as in Course Schedule II. order = [c for c in letters if need[c] == 0] for c in order: for y in after[c]: need[y] -= 1 if need[y] == 0: order.append(y) return "".join(order) if len(order) == len(letters) else "" # short means a cycle