解題說明
Short Encoding of Words
題目描述：給定一組單詞，可以建立一個「編碼字串」S 和一組索引 indices，其中每個 words[i] 等於 S.substr(indices[i]) 直到下一個 '#' 之前的子字串。若某個單詞是另一個單詞的後綴（suffix），它們可以共享同一段編碼。求最短的合法編碼字串 S 的長度。
解題思路：若單詞 A 是單詞 B 的後綴，則 A 不需要獨立編碼，B 的 '#' 終止符已隱含包含了 A。因此只需找出「不是任何其他單詞後綴」的單詞集合，答案為所有這些字串長度各加 1（'#'）的總和。
HashSet 刪除法：
- 將所有不重複單詞放入 HashSet。
- 對每個單詞，刪除其所有真後綴（
word[1:]、word[2:]、…）：若後綴存在於集合中說明此後綴可被當前單詞覆蓋，刪除之。 - 集合中剩餘的單詞即為「葉節點詞」，每個貢獻
len + 1。
Trie 等價理解：將所有單詞逆向（reverse）插入 Trie，則 Trie 的葉節點對應的即是不被其他任何詞覆蓋的單詞——每片葉對應一個必要的獨立編碼段。答案為所有葉節點深度之和（每個深度即為詞長）加上葉節點數（每個加一個 '#'）。
C++ 解法
複雜度分析
時間複雜度：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)，不需額外資料結構，但邊界情況較多。
延伸思考
- 若不要求用
'#'分隔，而是允許任意分隔字元（需保證不出現在單詞中），答案是否改變？ - 若允許任意子字串共享（而非只限後綴），問題等價於「最短超字串（Shortest Superstring）」，此時最優解如何求？
- 如何修改算法以同時支援前綴共享（即若 A 是 B 的前綴，A 也可被省略），例如建立雙端壓縮 Trie？