題目描述:給定按外星語言字典序排列的單詞列表,推導外星語言字元的排列順序。
解題思路:比較相鄰單詞找出字元順序關係(第一個不同的字元處,前詞的字元在後詞字元之前)。將這些關係建成有向圖,再做拓撲排序(Kahn's 演算法或 DFS)。若存在環則說明字典序矛盾,回傳空字串。特別注意前綴衝突:若前詞長度 > 後詞且是後詞的前綴,輸入無效。
時間複雜度:O(C) 其中 C 為所有單詞字元總數 — 建圖 O(C),拓撲排序 O(V+E)。
空間複雜度:O(1) — 字母表固定(最多 26 個字元)。
1. Collect all unique characters, init in-degree to 0 2. For each adjacent word pair (w1, w2): a. Find first differing position j b. Add edge w1[j] -> w2[j], increment in-degree of w2[j] c. If w1 is longer prefix of w2: return "" (invalid) 3. Kahn's BFS: enqueue chars with in-degree 0, process, decrement neighbors 4. If all chars processed, return order; else return "" (cycle)
DFS 拓撲排序 O(N):用 DFS 尋找環(同時檢測無效字序)並執行拓撲排序 — 邏輯更複雜但無需隊列。
暴力法:逐個字比較找出後繼關係,無法檢測無效輸入 — 不完整。