472. Concatenated Words

Hard

Description

給定一個字串陣列 words（不含重複），找出所有可以由陣列中至少兩個較短字串串接而成的字串。

Example:

Input: words = [“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”] Output: [“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]

Intuition#

對每個字串做 Word Break 判斷：能否被字典中的其他（更短）字串完全拼接。

本質上是對每個字串執行 LeetCode 139 Word Break 的檢查
先按長度排序，逐步加入字典
對每個字串用 DP 判斷是否能被已有字典中的字串拼接

Approaches#

1: DP Word Break for Each Word#

概念: 按長度排序，對每個字串做 Word Break DP 檢查
時間複雜度: O(n * L^2) 其中 L 為最長字串長度
空間複雜度: 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#

概念: 用 Trie 加速前綴匹配，DFS 搜尋所有可能的分割方式
時間複雜度: O(n * L^2)
空間複雜度: 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 推廣 — 對集合中每個字串做分詞檢查
關鍵技巧: 按長度排序後逐步加入字典，確保只用更短的字串來組合；Trie 可加速前綴查找但本題 HashSet 已足夠高效