The problem
You get words from an alien language, already sorted in that language’s alphabetical order. Work out an order of the letters consistent with it (or "" if the list is contradictory).
Input: ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf"
Picture it
Picture comparing neighbouring words in an alien dictionary. The first position where two neighbours differ tells us one rule: that letter of the first word comes before that letter of the second (“wrt” before “wrf” ⇒ t before f). Each rule is an arrow between letters. Then we put the letters in an order that follows every arrow (a topological sort).
How to recognise it
- You are given items already in sorted order under an unknown ranking, and must recover the ranking.
- Comparing two neighbours gives a rule of the form "this symbol comes before that one".
- Collecting the rules gives a directed graph, and any order that respects all of it is a valid answer.
- Contradictory data (a loop of rules) means no answer exists, so cycle detection is part of the problem.
Start with brute force
Try every ordering of the distinct letters, and for each one check whether the word list is sorted under it. Return the first ordering that works, or "" if none does.
from itertools import permutations
def alien_brute(words):
letters = sorted({ch for w in words for ch in w})
for perm in permutations(letters):
rank = {ch: i for i, ch in enumerate(perm)}
keys = [[rank[ch] for ch in w] for w in words]
if all(a <= b for a, b in zip(keys, keys[1:])):
return "".join(perm)
return ""
With k distinct letters there are k! orderings, each checked in O(total characters). For 10 letters that is 3.6 million checks; for the full 26 letters it is about 4 × 10^26, which is impossible. Space is O(k + total characters).
From brute force to the idea
- Find the waste. Almost all orderings fail on the very first pair of words that disagrees with them. The words already tell you what the ordering must satisfy.
- Read rules from neighbours. For two adjacent words, find the first position where the letters differ. If it is
xin the first word andyin the second, thenxcomes beforey. Later letters say nothing. Addytoafter[x]andbreak. - Adjacent pairs are enough. If every adjacent pair is in order, the whole list is in order, because "less than or equal" chains from word to word.
- Catch the prefix trap. If no letter differs (
for ... else), one word is a prefix of the other. A longer word before its own prefix ("abc"before"ab") is impossible, so return"". - Topologically sort the letters. Count
indegfor each letter, queue the letters with none, and repeatedly take one, lowering the count of the letters that come after it. This is Kahn's algorithm. - Check for a loop. If the order contains fewer letters than exist, some letters are on a cycle, so return
"".
The key idea: turn each adjacent pair into one "before" rule, then topologically sort the letters.
The key idea
Build “a before b” edges from adjacent words, then topologically sort. A cycle (or a longer word before its own prefix) means invalid.
Python solution
def alien_order(words):
after = {ch: set() for w in words for ch in w}
for a, b in zip(words, words[1:]):
for x, y in zip(a, b):
if x != y:
after[x].add(y) # x comes before y
break
else:
if len(a) > len(b): return "" # "abc" before "ab" is impossible
indeg = {ch: 0 for ch in after}
for x in after:
for y in after[x]: indeg[y] += 1
q = deque(ch for ch in after if indeg[ch] == 0)
order = ""
while q:
ch = q.popleft(); order += ch
for y in after[ch]:
indeg[y] -= 1
if indeg[y] == 0: q.append(y)
return order if len(order) == len(after) else ""LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(k!·C): every ordering is checked against the words | O(k + C) |
| Rules plus Kahn (shown code) | O(C + k + E): one pass over the characters of adjacent pairs, then a sort over k letters and E rules | O(k + E) for the rules and the queue |
Here C is the total number of characters, k is the number of distinct letters (at most 26) and E is the number of rules (at most one per adjacent pair).
Edge cases
- The classic sample (
["wrt","wrf","er","ett","rftt"]): returns a valid order such as"wertf". - A prefix in the wrong order (
["abc","ab"]): returns"". - A loop of rules (
["z","x","z"]): returns"", because z must precede x and x must precede z. - No rules at all (
["ab","ab"]or one word): any order of the letters is valid. The shown code returns all letters, and the order among unconstrained letters may differ from run to run. - Letters that appear in no rule are still included, because
afterstarts with every letter in every word. - Empty list: returns
"".dequemust be imported.
Common mistakes
- Comparing every letter of two words instead of stopping at the first difference.
- Comparing non-adjacent words, or skipping the adjacent ones.
- Forgetting the prefix case, so an impossible list gets an answer.
- Leaving out letters that appear in no rule.
- Adding the same rule twice to a list and double-counting the in-degree (the shown code uses sets to avoid this).
Return True only if exactly one letter order is consistent with the words, and False if there are several orders or none. Describe what changes, then write it if you like.
Compare with our answer
Build the rules the same way. In Kahn's algorithm the order is unique exactly when there is never a choice: the queue never holds two letters at once, and every letter ends up being taken.
def order_is_unique(words):
after = {ch: set() for w in words for ch in w}
for a, b in zip(words, words[1:]):
for x, y in zip(a, b):
if x != y:
after[x].add(y)
break
else:
if len(a) > len(b):
return False
indeg = {ch: 0 for ch in after}
for x in after:
for y in after[x]:
indeg[y] += 1
q = deque(ch for ch in after if indeg[ch] == 0)
done = 0
while q:
if len(q) > 1:
return False
ch = q.popleft()
done += 1
for y in after[ch]:
indeg[y] -= 1
if indeg[y] == 0:
q.append(y)
return done == len(after)
order_is_unique(["wrt","wrf","er","ett","rftt"]) is True, and order_is_unique(["ab","ab"]) is False. Time O(C + k + E), space O(k + E).
A strong answer mentions: checking the queue size at each step, that two ready letters mean two possible orders, and still returning False for a cycle or prefix conflict.
1. Several judges each rank only some of the contestants, in lists such as [A, C] and [C, B]. You must produce one overall ranking that agrees with every list, or report that none exists. Which approach fits best?
Each list gives precedence rules, and an order that respects all of them is a topological order, which also exposes contradictions as cycles. Average positions can break a rule, and BFS or unions ignore direction.
2. Why is it enough to compare only adjacent words in the list?
If each word is at or before the next, the whole list is sorted by transitivity, so any further rules from distant pairs are consequences of the adjacent ones. Far-apart words can have different first letters without adding anything new.
3. A learner deletes the else: block (the if len(a) > len(b): return "" check). Which input now returns a wrong answer?
The words abc and ab give no differing letter, so without the prefix check no rule exists and the function returns all three letters instead of "". The other inputs never reach the removed block with a longer word first.
Score 60% or more and the lesson is marked complete.