題目描述:給定一個字串陣列 words,找出所有「連接詞」——即能由陣列中其他至少 2 個單字(可重複使用)拼接而成的字串。例如 "catsdogcats" 可由 "cats" + "dog" + "cats" 拼成。
解題思路:結合 Trie 與動態規劃(類似 Word Break)高效求解。
Trie 建立:將所有單字插入 Trie,作為字典查詢結構。
DP 判斷:對每個單字 word(長度為 L),定義 dp[i] 表示 word[0..i-1] 是否能由字典中的單字拼成,且使用的單字數 splits 記錄分割次數。
具體做法:初始化 dp[0] = true(空字串基底),對每個位置 i(dp[i] 為 true),從位置 i 出發在 Trie 中逐字元向下走,每當走到一個完整單字的結尾節點 j,若 dp[i] 為 true 且此分割後使 splits >= 2(確保至少用了 2 個單字),則更新 dp[j] = true。
最終若 dp[L] 為 true(且整個單字本身不是「拼成自身」的情形由 splits >= 2 保證),則此單字為連接詞。
時間複雜度:O(n × L²) — 對 n 個單字,每個長度最大為 L,DP 需要 O(L) 個起點,每個起點在 Trie 中走至多 L 步,故每個單字需要 O(L²)。Trie 建立為 O(n × L)。
空間複雜度:O(n × L) — Trie 節點數量為所有單字字元總數;DP 陣列為 O(L),重複使用。
Function findAllConcatenatedWordsInADict(words):
Build Trie from all words
result = []
For each word in words:
L = length of word
dp[0..L] = false; dp[0] = true
splits[0..L] = 0
For i from 0 to L-1:
If dp[i] is false: skip
node = root
For j from i to L-1:
Move node to node.children[word[j]]
If node is null: break
If node.isEnd:
newSplits = splits[i] + 1
If newSplits > splits[j+1]:
splits[j+1] = newSplits
dp[j+1] = true
If dp[L] is true AND splits[L] >= 2:
Add word to result
Return result純 DP + 雜湊集合(Word Break 變形):用 unordered_set<string> 存所有單字,對每個單字用 Word Break DP 判斷。每次切割需要字串擷取(substr),時間複雜度 O(n × L²),但雜湊計算的常數係數較大;Trie 方法在 Trie 走訪時避免了字串建立,實際較快。
DFS + 記憶化搜尋:從每個位置出發,嘗試所有前綴是否為字典中的單字,遞迴向右推進並記錄已搜尋過的位置。等價於 DP,但以遞迴形式實作,memo[i] 記錄從位置 i 出發是否可拼成剩餘部分。需額外傳遞「已用單字數 >= 1」的狀態,確保至少 2 個單字。
排序後剪枝:先按長度排序,短的單字先加入字典,再逐一判斷較長的單字。如此一來,較短的單字必然已在字典中,且連接詞的長度必然嚴格大於其組成單字。可省去「判斷單字本身不構成自身連接」的複雜邏輯,但需注意相同長度的邊界情況。