Core Insight Improve a node’s known cost only when a newly discovered path is genuinely better.
Common Pitfall Discard stale priority-queue entries instead of expanding them a second time.
Description
Determine the order of characters in an alien language.
Constraints
- Time Complexity:
O(C) - Space Complexity:
O(1)
Tags
arraystringdfsbfsgraphtopological-sort
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize distances and a frontier.
- Take the cheapest candidate.
- Relax each outgoing edge.
- Repeat until the target or all reachable nodes are settled.
def alienOrder(words):
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break
visit = {}
res = []
def dfs(c):
if c in visit:
return visit[c]
visit[c] = True
for nei in adj[c]:
if dfs(nei): return True
visit[c] = False
res.append(c)
for c in adj:
if dfs(c): return ""
res.reverse()
return "".join(res)