題目描述:給定一組單詞,可以建立一個「編碼字串」S 和一組索引 indices,其中每個 words[i] 等於 S.substr(indices[i]) 直到下一個 '#' 之前的子字串。若某個單詞是另一個單詞的後綴(suffix),它們可以共享同一段編碼。求最短的合法編碼字串 S 的長度。
解題思路:若單詞 A 是單詞 B 的後綴,則 A 不需要獨立編碼,B 的 '#' 終止符已隱含包含了 A。因此只需找出「不是任何其他單詞後綴」的單詞集合,答案為所有這些字串長度各加 1('#')的總和。
HashSet 刪除法:
word[1:]、word[2:]、…):若後綴存在於集合中說明此後綴可被當前單詞覆蓋,刪除之。len + 1。Trie 等價理解:將所有單詞逆向(reverse)插入 Trie,則 Trie 的葉節點對應的即是不被其他任何詞覆蓋的單詞——每片葉對應一個必要的獨立編碼段。答案為所有葉節點深度之和(每個深度即為詞長)加上葉節點數(每個加一個 '#')。
時間複雜度:O(N × L²) — 對每個長度 L 的單詞,生成 L-1 個後綴(每個後綴長度為 O(L)),所有 N 個單詞共 O(N × L²)。HashSet 查找與刪除均攤 O(L)(字串雜湊)。
空間複雜度:O(N × L) — HashSet 儲存所有不重複單詞。若使用 Trie 方法,空間同樣為 O(N × L × 26)(節點數 × 子指標)。
minimumLengthEncoding(words):
1. wordSet = HashSet(words) // 去重
2. For each word in words:
For i = 1 to len(word)-1:
Remove word[i..] from wordSet // 刪除所有真後綴
3. ans = 0
4. For each w in wordSet:
ans += len(w) + 1 // 詞長 + '#'
5. Return ans
--- Trie 等價做法 ---
BuildReversedTrie(words):
1. For each word: insert reverse(word) into Trie
2. Mark each TrieNode's depth
CountLeaves(Trie):
1. DFS; for each leaf node at depth d: ans += d + 1
2. Return ans逆序 Trie + 葉節點統計:將每個單詞逆序後插入 Trie,Trie 中所有葉節點即對應必要的獨立編碼詞。DFS 統計所有葉節點的深度(即詞長)之和再加葉節點數(每個 '#')。時間 O(N × L),空間 O(N × L × 26)。比 HashSet 法時間更優(無須 substr),結構也更直觀地體現後綴共享。
排序 + 後綴比對:將所有單詞按長度降序排列,依序將每個詞加入結果集;若新詞不是結果集中任何詞的後綴,則加入。後綴判斷可用 endsWith。時間 O(N log N + N × L),但判斷後綴需遍歷結果集,最壞 O(N²× L)。
字典序排序 + 相鄰比較:將所有單詞逆序後排序,相鄰詞若前者是後者的前綴(即原始後綴關係)則可合併。時間 O(N × L × log N),不需額外資料結構,但邊界情況較多。
'#' 分隔,而是允許任意分隔字元(需保證不出現在單詞中),答案是否改變?