139. Word Break

Medium

Description

給定一個字串 s 和一個字典 wordDict，判斷 s 是否可以被拆分為一個或多個字典中的單詞。字典中的單詞可以重複使用。

Example:

Input: s = “leetcode”, wordDict = [“leet”,“code”] Output: true

Intuition#

如果 dp[j] 為 true 且 s[j..i] 在字典中，則 dp[i] 為 true
用 HashSet 加速字典查詢
可以用字典中最長單詞的長度來限制回溯範圍

Approaches#

1: Top-Down Memoization#

概念: 遞迴嘗試每個前綴是否在字典中，若是則遞迴處理剩餘部分
時間複雜度: O(n^2 * m) — n 為字串長度，m 為子字串比較時間
空間複雜度: O(n)

class Solution {
    fun wordBreak(s: String, wordDict: List<String>): Boolean {
        val wordSet = wordDict.toHashSet()
        val memo = HashMap<Int, Boolean>()
        fun dp(start: Int): Boolean {
            if (start == s.length) return true
            memo[start]?.let { return it }
            for (end in start + 1..s.length) {
                if (s.substring(start, end) in wordSet && dp(end)) {
                    memo[start] = true
                    return true
                }
            }
            memo[start] = false
            return false
        }
        return dp(0)
    }
}

⭐2: Bottom-Up DP#

概念: dp[i] 表示 s[0..i-1] 是否可拆分，對每個位置 i 檢查所有可能的最後一個單詞
時間複雜度: O(n^2 * m)
空間複雜度: O(n)

class Solution {
    fun wordBreak(s: String, wordDict: List<String>): Boolean {
        val wordSet = wordDict.toHashSet()
        val dp = BooleanArray(s.length + 1)
        dp[0] = true
        for (i in 1..s.length) {
            for (j in 0 until i) {
                if (dp[j] && s.substring(j, i) in wordSet) {
                    dp[i] = true
                    break
                }
            }
        }
        return dp[s.length]
    }
}

🔑 Takeaways#

Pattern: 字串分割 DP — 嘗試所有切割位置，用布林 DP 判斷可行性
關鍵技巧: 用 HashSet 存字典加速查詢；內迴圈找到一個有效拆分就可以 break