題目描述:給定字串陣列 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"],插入後:
時間複雜度: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 空間更差,但實作最簡單。
count 節點如何維護?刪除一個字串需要哪些步驟?