解題說明
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 節點的子節點儲存方式以節省記憶體?