解題說明
Verifying an Alien Dictionary
題目描述：
在一個外星語言中，字母的排列順序與英文不同。給定一個「外星字典序」order（26 個小寫字母的排列）和一個字串陣列 words，判斷 words 是否按照此外星字典序排列。
解題思路：
- 建立字母到順序的映射：將
order轉為一個長度 26 的陣列，rank[c]= 字母c在外星字典中的位置。 - 逐對比較相鄰單詞
words[i]和words[i+1]：- 逐字元比較，找到第一個不同的字元。
- 若
rank[words[i][j]] > rank[words[i+1][j]]，則不合法。 - 若
rank[words[i][j]] < rank[words[i+1][j]]，則合法，進入下一對。 - 若所有字元相同但
words[i]較長，則不合法（例如"apple"應排在"app"之後）。
C++ 解法
複雜度分析
時間複雜度：O(n * m) — 其中 n 是單詞數量，m 是單詞的最大長度。每對相鄰單詞最多比較 m 個字元。
空間複雜度：O(1) — rank 陣列大小固定為 26。
虛擬碼
1. Build rank array: for each position i in order, rank[order[i]] = i. 2. For each adjacent pair (words[i], words[i+1]): a. Compare character by character using rank. b. At first difference: if rank[a[j]] > rank[b[j]], return false. c. If all compared characters are equal and len(a) > len(b), return false. 3. Return true if all pairs are valid.
其他解法
自定義比較器 + 排序驗證：O(n * m * log n) 時間。用外星字典序定義比較函數，排序後與原陣列比較。正確但效率較低。
字串映射轉換：O(n * m) 時間。將每個單詞的字母替換為標準順序的字母，然後直接用標準字串比較。額外空間 O(n * m)。
延伸思考
- 如果不給定完整的外星字典序，而是給定一組單詞要求推導出字典序（LeetCode 269），該如何解決？
- 為什麼只需要比較相鄰的單詞對，而不需要比較所有可能的單詞對？
- 如果外星語言有超過 26 個字母（例如 Unicode 字元），資料結構需要如何調整？