題目與適用情境
給定一個非空小寫 ASCII 字串陣列 words，陣列聲稱已依某個未知字母表排序。請回傳一個包含 輸入中所有不同字元、且每個字元恰好出現一次的順序，使整份單字清單保持有序。若不存在這種 順序，回傳空字串。存在多個可行字母表時，回傳任意一個即可。
本題假設單字數不超過 10,000，總字元數不超過 100,000；這些是面試練習限制，不代表特定平台 上限。["wrt", "wrf", "er", "ett", "rftt"] 的一個答案是 "wertf"。 ["abc", "ab"] 無解，因為較長單字排在自身前綴之前；["z", "x", "z"] 同時要求 z < x 和 x < z，也無解。
難點發生在拓撲排序之前。輸入只有已排序單字，圖的邊需要推導。解法必須只擷取字典順序真正 支援的限制，保留沒有邊的字元，並分別處理前綴矛盾與有向環。
面試官在評估什麼
第一個訊號是能否從相鄰單字的第一個不同字元推導邊。"wrt" 排在 "wrf" 前面，只能證明 t < f。第一個差異已決定這對單字的字典順序，後續位置無法再提供這對單字的字元先後關係。
第二個訊號是前綴規則。共同部分完全相同時，較短單字必須在前。"ab" 位於 "abc" 前面 合法且不新增邊；"abc" 位於 "ab" 前面與任何字母表都衝突。單獨執行拓撲排序無法發現 這個問題，因為這對單字不會產生不同字元。
第三個訊號是建圖是否完整。每個出現過的字元都要成為節點，包括單字中沒有任何邊的孤立字元。 同一條邊出現多次時，入度只能增加一次；為每個來源字元使用相鄰集合可保持相鄰關係與入度一致。
最後評估證明與驗證。Kahn 演算法只有處理完全部節點才能回傳完整順序；結果較短表示剩餘圖中 有環。某一步同時出現多個零入度字元，代表證據無法確定唯一字母表，但在基礎題契約中仍然有效。
回答前要先確認的問題
- 輸入是否包含字母表中的所有字元？ 本解法只排列單字中出現過的字元。沒有外部字母表定義，
就無法補充或放置未出現字元。
- 任意有效順序都可以嗎？ 基礎題允許任意答案。若要求依一般字元順序最小，需要最小堆，
複雜度也會改變。
- 如何表示無解？ 本題對無效前綴和環都回傳空字串。正式 API 可以回傳結構化原因與證據。
- 字元的定義是什麼？ 基礎輸入只包含小寫 ASCII。Unicode 碼點或字素叢集需要先約定斷詞規則。
- 單字可以重複嗎？ 可以。兩個相同的相鄰單字不增加限制，也不會讓輸入無效。
- 必須存在唯一字母表嗎？ 不需要。追問可透過每一步零入度候選數判斷唯一性。
- 陣列可以為空嗎？ 本版本至少包含一個非空單字。若允許空輸入，要先確認回傳空字母表還是
回報請求無效。
30 秒回答架構
「我會為每個不同字元建立節點。逐對比較相鄰單字，只掃描到第一個不同位置，並從前一個單字的 字元向後一個單字的字元連邊。若沒有不同字元且前一個單字較長，就出現較長單字排在自身前綴 之前的矛盾，直接回傳空字串。建圖時對邊去重並維護入度，再從所有零入度字元開始執行 Kahn 拓撲排序。處理完所有節點就得到滿足全部限制的順序；結果較短表示存在環。總時間為輸入字元數 加圖規模的線性複雜度，多種拓撲順序都可作為答案。」
分步驟深入解答
記 C 為所有單字的總字元數，U 為不同字元數，E 為不同先後邊數。先為每個已出現字元建立 相鄰集合 graph[ch] 和初始值為零的 indegree[ch]。這個步驟必須在比較單字前完成：一個字元 即使沒有任何限制也是合法節點，不能只從邊的端點收集字元。
只比較相鄰單字就足夠。若回傳的字母表能證明每一對相鄰單字有序，遞移性會保證整份清單有序； 同時也避免比較平方數量的單字對。對 first 與 second 掃描到較短長度：
- 第一次遇到
first[i] != second[i]時，加入first[i] -> second[i]，並停止比較該詞對。 - 所有共同位置都相同且
first較長時，回傳空字串。 - 所有共同位置都相同且
first不較長時，不新增邊。
只有新邊插入相鄰集合時才增加目標字元入度。例如 "za" < "zb" 與 "ca" < "cb" 都 推出 a -> b。若將其計數兩次，移除 a 後 b 的入度仍大於零，合法輸入會被誤判成環。
Kahn 演算法把所有零入度字元放入佇列。它維護兩個不變量：每個未處理字元的入度等於其他未處理 字元指向它的邊數；佇列恰好包含沒有未處理前驅的字元。取出佇列前端字元是安全的，接著走訪其 出邊並減少鄰居入度；鄰居的最後一個前驅消失時進入佇列。
from collections import deque
def alien_order(words: list[str]) -> str:
graph = {char: set() for word in words for char in word}
indegree = {char: 0 for char in graph}
for first, second in zip(words, words[1:]):
limit = min(len(first), len(second))
for index in range(limit):
before = first[index]
after = second[index]
if before == after:
continue
if after not in graph[before]:
graph[before].add(after)
indegree[after] += 1
break
else:
if len(first) > len(second):
return ""
ready = deque(
char for char, degree in indegree.items() if degree == 0
)
order: list[str] = []
while ready:
char = ready.popleft()
order.append(char)
for neighbor in graph[char]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
ready.append(neighbor)
return "".join(order) if len(order) == len(indegree) else ""正確性分成兩層。建圖具有可靠性：每條邊都來自相鄰單字的第一個差異，因此任何可行字母表都 必須滿足它；前綴檢查排除了沒有不同字元卻依然無序的唯一相鄰情境。拓撲排序也具有可靠性：佇列 不變量保證輸出字元位於所有已推導前驅之後。於是每一對相鄰單字都有序，整份清單也有序。
若演算法輸出少於 U 個字元，剩餘節點的入度都大於零。從任意剩餘節點反覆沿入邊前進，在有限 圖中必然再次遇到某個節點，重複部分構成有向環，線性字母表無法滿足它。反過來，無環圖總有 零入度節點，所以 Kahn 演算法最終會處理全部節點並回傳有效順序。
初始化節點並掃描相鄰單字需要 O(C)，Kahn 演算法各處理節點和不同邊一次，總時間為 O(C + U + E)，額外空間為 O(U + E)。小寫 ASCII 下 U 最多為 26，但保留符號表達更方便 套用到其他字母表。
多解時，測試應驗證性質。非空結果必須恰好包含全部不同字元一次；建立字元排名後，依回傳順序 重新比較每對相鄰單字，並單獨檢查較長單字是否排在自身前綴前。測試要涵蓋單一單字、重複單字、 孤立字元、重複邊證據、合法前綴、無效前綴、環、長鏈，以及同時存在多個零入度節點的圖。
三色 DFS 也是正確替代方案：遇到灰色節點表示環，離開遞迴時記錄節點並反轉後序結果。Kahn 演算法可直接從候選集合觀察多解，也沒有遞迴深度問題，因此更適合本題契約。
高品質示範回答
「我先從已排序單字中擷取偏序。每個出現過的字元都建立節點，即使它沒有任何邊。逐對比較相鄰 單字並找到第一個不同字元：例如 wrt 與 wrf 推出 t -> f，後續位置無法再影響這對單字 的比較。若沒有不同字元，而前一個單字較長，例如 abc 位於 ab 前面，輸入已經矛盾。
相鄰表使用集合，同一先後關係只增加一次入度。接著執行 Kahn 演算法：所有零入度字元先進入 佇列，每次輸出一個字元、刪除它的出邊，並在鄰居入度降為零時加入佇列。佇列中的字元在未處理 圖中沒有前驅，所以每次選擇都不會違反已知限制。
若結果長度等於不同字元數，每條推導出的邊都得到滿足，加上前綴檢查即可證明每對相鄰單字有序， 進而證明整份清單有序。若長度更短，剩餘圖存在環，沒有任何字母表能解釋輸入。時間複雜度是 O(C + U + E)，空間複雜度是 O(U + E)。我會測試無效前綴、兩邊構成的環、同一邊重複出現、 單一單字和多解；多解案例驗證順序性質，不固定比較某一個字串。」
常見錯誤
- 把詞對中每個不同位置都連邊 → 第一個差異後的位置不再參與字典順序判斷 → **只加入第一個
差異對應的邊並立即停止。**
- 只執行拓撲排序 →
"abc"位於"ab"前面時沒有邊可暴露錯誤 → **比較詞對時檢查較長
單字先於自身前綴的矛盾。**
- 只為邊的端點建立節點 → 孤立字元從答案消失 → 為所有出現過的字元預先建立節點。
- 重複邊重複增加入度 → 合法節點永遠無法降到零入度 → 使用相鄰集合，只在首次插入時增加。
- 佇列為空就回傳部分結果 → 有環輸入被回報為成功 → 要求結果長度等於不同字元數。
- 只接受一個固定字串 → 一個偏序可能有多種線性延伸 → 檢查字元集合、邊和單字相對順序。
- 比較所有單字對 → 單字數量維度可能出現平方級工作 → 相鄰比較已足以建立清單有序性。
- 把多解當成無效 → 多個字母表可同時解釋現有證據 → 基礎契約下回傳任意有效順序。
追問與回答
追問 1：如何判斷字母表是否唯一？
Kahn 演算法每次取出前檢查候選集合。只要某一步有兩個以上零入度字元，就至少存在兩種選擇順序， 證據無法確定唯一字母表。若每一步候選數都恰好為一且處理完全部節點，順序唯一；提前出現空集合 仍表示有環。
追問 2：如何回傳一般字元順序下最小的有效結果？
把普通佇列換成依宿主語言字元順序排列的最小堆。每次選擇目前可行字元中的最小者，可用交換論證 證明得到最小線性延伸。時間變成 O(C + E + U log U)；這個排序只是外部打破平手的規則，不屬於 外星字母表本身。
追問 3：如何回傳可操作的無效原因？
前綴矛盾可回傳相鄰單字及其索引。Kahn 演算法停滯後，在剩餘圖上執行帶父指標的三色 DFS，遇到 灰色節點時還原一條環。結構化結果可區分 invalid_prefix、cycle 與 valid，不必讓空字串 承擔全部語意。
追問 4：可以串流處理單字嗎？
保留前一個單字；每讀到下一個單字就補充節點並推導這一對相鄰限制。圖和入度仍要保存到串流結束， 因為後續證據可能增加前驅或形成環。除非資料來源提供明確結束邊界，否則不能提前確認最終拓撲順序。
追問 5：如何列舉所有有效字母表？
對目前所有零入度字元回溯：選擇一個、暫時刪除其出邊、遞迴，再還原狀態。這樣只列舉合法順序， 但輸出數量可能接近 U!；實作前應確認字母表規模或最大輸出數量。
追問 6：Unicode 單字需要改什麼？
先定義比較單位。碼點不一定等於使用者看到的字元，地區排序還可能處理正規化形式或多碼點序列。 依題目約定把單字切成字母表符號，只在契約要求時正規化，再對這些 token 執行同一套圖演算法。 缺少該契約時，「字元順序」本身沒有完整定義。