Alien Alphabet Order
Problem
A recovered dictionary from an unknown language uses lowercase English letters, but in a different alphabetical order. Given its words, already sorted by that unknown order, return a string of every letter that appears, arranged in an order consistent with the dictionary. When several letters could come next, take the one that is earliest in the English alphabet, so the answer is unique. If no order fits the words, return an empty string. There are up to 100 words of up to 100 letters each.
Examples
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Why: the neighbouring pairs give t before f, w before e, r before t and e before rInput: words = ["z", "x", "z"]
Output: ""
Why: z must come before x and x before z, a contradictionInput: words = ["abc", "ab"]
Output: ""
Why: edge case, a word cannot come before its own prefix in any orderHints
0 / 3
Only neighbouring words tell you anything, and only at the first position where they differ: that letter pair says which letter comes first. Everything after it says nothing.
Each such pair is a directed edge between two letters. A valid alphabet is an ordering where every edge points forward, which is a topological order.
Collect every letter, add one edge per neighbouring pair (and fail if a longer word comes before its own prefix), then run Kahn's algorithm with a min-heap as the queue so the smallest ready letter goes next. If fewer letters come out than went in, there is a cycle.
Solution
Comparing neighbouring words at their first differing position gives one ordering fact each, an edge from the earlier letter to the later one; comparing words further apart adds nothing new, since the order is transitive. Two cases break the input: a word followed by its own proper prefix, and a cycle among the edges. Kahn's algorithm then outputs letters with no remaining incoming edge, and using a min-heap as its queue picks the earliest English letter whenever there is a choice, which makes the answer unique. If the heap empties before every letter is placed, the leftover letters sit on a cycle. With L total letters in the words and at most 26 distinct letters, time is O(L), and space is O(1) beyond the input.
import heapq
def alien_order(words):
letters = {ch for w in words for ch in w}
after = {ch: set() for ch in letters}
indegree = {ch: 0 for ch in letters}
for a, b in zip(words, words[1:]):
for x, y in zip(a, b):
if x != y:
if y not in after[x]:
after[x].add(y) # x comes before y
indegree[y] += 1
break
else:
if len(a) > len(b):
return "" # a word before its own prefix
ready = [ch for ch in letters if indegree[ch] == 0]
heapq.heapify(ready)
out = []
while ready:
ch = heapq.heappop(ready) # smallest letter that is free to go
out.append(ch)
for nxt in after[ch]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
heapq.heappush(ready, nxt)
return "".join(out) if len(out) == len(letters) else "" # leftovers mean a cycle
print(alien_order(["wrt", "wrf", "er", "ett", "rftt"])) # -> wertf
print(alien_order(["z", "x", "z"])) # -> ""
print(alien_order(["abc", "ab"])) # -> ""
print(alien_order(["ab", "adc"])) # -> abcdStuck on the idea rather than the code? Topological Sort covers it.