給定一個字串陣列
words（不含重複），找出所有可以由陣列中至少兩個較短字串串接而成的字串。
Example:
Input: words = [“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”] Output: [“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]
Intuition
TIP
對每個字串做 Word Break 判斷：能否被字典中的其他（更短）字串完全拼接。
- 本質上是對每個字串執行 LeetCode 139 Word Break 的檢查
- 先按長度排序，逐步加入字典
- 對每個字串用 DP 判斷是否能被已有字典中的字串拼接
Approaches
1. DP Word Break for Each Word — O(n * L^2) / O(n * L)
- Idea: 按長度排序，對每個字串做 Word Break DP 檢查
- Time:
O(n * L^2)其中 L 為最長字串長度 - Space:
O(n * L)
class Solution {
fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
val dict = HashSet<String>()
val result = mutableListOf<String>()
words.sortBy { it.length }
for (word in words) {
if (word.isEmpty()) continue
if (canForm(word, dict)) {
result.add(word)
}
dict.add(word)
}
return result
}
private fun canForm(word: String, dict: Set<String>): Boolean {
if (dict.isEmpty()) return false
val n = word.length
val dp = BooleanArray(n + 1)
dp[0] = true
for (i in 1..n) {
for (j in 0 until i) {
if (dp[j] && word.substring(j, i) in dict) {
dp[i] = true
break
}
}
}
return dp[n]
}
}⭐ 2. Trie + DFS — O(n * L^2) / O(n * L)
- Idea: 用 Trie 加速前綴匹配，DFS 搜尋所有可能的分割方式
- Time:
O(n * L^2) - Space:
O(n * L)(Trie 空間)
class Solution {
class TrieNode {
val children = arrayOfNulls<TrieNode>(26)
var isEnd = false
}
fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
val root = TrieNode()
for (w in words) {
if (w.isEmpty()) continue
var node = root
for (c in w) {
val idx = c - 'a'
if (node.children[idx] == null) node.children[idx] = TrieNode()
node = node.children[idx]!!
}
node.isEnd = true
}
val result = mutableListOf<String>()
for (word in words) {
if (word.isNotEmpty() && dfs(word, 0, root, 0)) {
result.add(word)
}
}
return result
}
private fun dfs(word: String, start: Int, root: TrieNode, count: Int): Boolean {
if (start == word.length) return count >= 2
var node = root
for (i in start until word.length) {
val idx = word[i] - 'a'
node = node.children[idx] ?: return false
if (node.isEnd && dfs(word, i + 1, root, count + 1)) return true
}
return false
}
}🔑 Takeaways
- Pattern: Word Break 推廣 — 對集合中每個字串做分詞檢查
- Key trick: 按長度排序後逐步加入字典，確保只用更短的字串來組合；Trie 可加速前綴查找但本題 HashSet 已足夠高效