解題說明
Sum of Prefix Scores of Strings
題目描述：給定字串陣列 words，對每個 words[i] 計算其「前綴分數總和」：words[i] 的每個前綴（長度 1 到 words[i].length()）的分數是「words 中有多少個字串以此前綴開頭」的數量，將所有前綴的分數加總得到 ans[i]。
解題思路（Trie + 計數節點）：
對每個前綴暴力統計有多少字串以它開頭的時間為 O(n² · L)，過慢。使用 Trie 可在建構時一次性記錄所有前綴的覆蓋數量。
建構階段：在 Trie 的每個節點加入 count 欄位。插入字串時，沿路徑經過的每個節點的 count 加 1。插入完所有字串後，節點的 count 值恰好等於「有多少字串以該節點對應前綴開頭」。
查詢階段：對每個 words[i]，沿 Trie 路徑逐字元走，將沿途所有節點的 count 累加，即為 ans[i]。
範例：words = ["abc", "ab", "bc", "b"]，插入後：
- 根→'a' 節點 count=2，根→'b' 節點 count=2
- 'a'→'b' 節點 count=2，'a'→'b'→'c' 節點 count=1
- 對 "abc" 查詢：count('a') + count('ab') + count('abc') = 2 + 2 + 1 = 5
C++ 解法
複雜度分析
時間複雜度：O(n · L) — 插入所有字串需 O(n · L) 時間（n 個字串，平均長度 L）；查詢同樣需 O(n · L)；整體線性於輸入大小。
空間複雜度：O(n · L · 26) — Trie 最多 n × L 個節點，每個節點有 26 個子指標；最壞情況（所有字串無共用前綴）為 O(n · L)。
虛擬碼
1. Initialize Trie with one root node (count=0, children all -1).
2. For each word in words:
a. cur = root
b. For each char c in word:
- If no child for c: create new node.
- Move cur to child[c].
- Increment trie[cur].count.
3. For each word in words:
a. cur = root, score = 0
b. For each char c in word:
- cur = child[c] of cur.
- score += trie[cur].count.
c. ans[i] = score.
4. Return ans.其他解法
方法二：暴力雙重迴圈
對每個字串 words[i] 的每個前綴，遍歷所有其他字串判斷是否以此前綴開頭。時間 O(n² · L²)，空間 O(1)（不計輸出）。在 n = 1000、L = 1000 時就已超時，僅適合小測資驗證。
方法三：排序 + 相鄰比較
將所有字串排序，相同前綴的字串必定相鄰。對每個字串的每個前綴，用二分搜尋找到以此前綴開頭的字串區間（lower_bound / upper_bound），區間大小即為分數。時間 O(n · L · log n)，空間 O(n · L)（字串儲存）。比 Trie 慢但不需要自行實作 Trie。
方法四：雜湊表計數
遍歷所有字串，對每個字串的每個前綴在 unordered_map<string, int> 中計數 +1。建構後對每個字串查詢所有前綴的分數並累加。時間 O(n · L)（均攤），空間 O(n · L²)（所有前綴字串的儲存量）。比 Trie 空間更差，但實作最簡單。
延伸思考
- 若問題改為「後綴分數總和」（以某後綴結尾的字串數量），只需將所有字串反轉後插入 Trie，演算法本身是否無需改變？
- 若需要支援動態插入或刪除字串，Trie 的
count節點如何維護？刪除一個字串需要哪些步驟？ - 若字元集從小寫字母（26）擴展到 Unicode（約 100 萬個字符），應如何改造 Trie 節點的子節點儲存方式以節省記憶體？