Description
Infer a valid ordering of lowercase letters from words sorted in an unknown alphabet. Return an empty string if contradictory. Any valid ordering is accepted.
Solution
from collections import deque
def alien_order(words):
edges = {c:set() for word in words for c in word}
degree = dict.fromkeys(edges, 0)
for a,b in zip(words, words[1:]):
if len(a) > len(b) and a.startswith(b):
return ''
for x,y in zip(a,b):
if x != y:
if y not in edges[x]:
edges[x].add(y)
degree[y] += 1
break
queue = deque(c for c in edges if degree[c] == 0)
result = []
while queue:
c = queue.popleft()
result.append(c)
for d in sorted(edges[c]):
degree[d] -= 1
if degree[d] == 0:
queue.append(d)
return ''.join(result) if len(result) == len(edges) else ''Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[["ab","ac"]]- Output
"abc"
b must precede c; abc is one valid order.
Example 2
- Input
[["abc","ab"]]- Output
""
A longer word cannot precede its own prefix.
Example 3
- Input
[["z","x","z"]]- Output
""
The constraints require both z before x and x before z.
Approach
Compare adjacent words only until the first mismatch, add a directed constraint, then topologically sort letters.
Time & space
O(S + V + E) time and O(V + E) space for S total characters; V <= 26.