給定一個字串
s和一個字典wordDict，判斷s是否可以被拆分為一個或多個字典中的單詞。字典中的單詞可以重複使用。
Example:
Input: s = “leetcode”, wordDict = [“leet”,“code”] Output: true
Intuition
TIP
dp[i] 代表 s[0..i-1] 是否可被拆分，對每個位置回頭找是否存在有效的切割點。
- 如果
dp[j]為 true 且s[j..i]在字典中，則dp[i]為 true - 用 HashSet 加速字典查詢
- 可以用字典中最長單詞的長度來限制回溯範圍
Approaches
1. Top-Down Memoization — O(n^2 * m) / O(n)
- Idea: 遞迴嘗試每個前綴是否在字典中，若是則遞迴處理剩餘部分
- Time:
O(n^2 * m)— n 為字串長度，m 為子字串比較時間 - Space:
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 — O(n^2 * m) / O(n)
- Idea:
dp[i]表示s[0..i-1]是否可拆分，對每個位置i檢查所有可能的最後一個單詞 - Time:
O(n^2 * m) - Space:
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 判斷可行性
- Key trick: 用 HashSet 存字典加速查詢；內迴圈找到一個有效拆分就可以 break