Open
Description
状态定义
dp[i]: 字符串 s 的前 i 个字符子串 s[0..i-1] 是否由单词表组成。
状态转移方程
dp[i] = dp[j] && check(s[j..i-1])
- 使用 j 对字符串进行分割，分割成
[0..j-1](dp[j]) 和[j, i-1]。 check(s[j..i-1])：代表子串s[j..i-1]是否出现在字典中。
状态转移方程需要满足：
dp[j]为真- 检查
s[j..i-1]是否在单词表中
初始化
dp[0] = true，空串且合法。
const wordBreak = function(s, wordDict){
const wordDictSet = new Set(wordDict)
const len = s.length
const dp = new Array(len + 1).fill(false)
dp[0] = true
for (let i = 1; i <= len; i++) {
for (let j = i - 1; j >= 0; j--) {
const suffix = s.slice(j, i)
if (wordDictSet.has(suffix) && dp[j]) {
dp[i] = true
break
}
}
}
return dp[len]
}- 时间复杂度：O(n^2)
- 空间复杂度：O(n)