- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
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，空串且合法。
constwordBreak=function(s,wordDict){constwordDictSet=newSet(wordDict)constlen=s.lengthconstdp=newArray(len+1).fill(false)dp[0]=truefor(leti=1;i<=len;i++){for(letj=i-1;j>=0;j--){constsuffix=s.slice(j,i)if(wordDictSet.has(suffix)&&dp[j]){dp[i]=truebreak}}}returndp[len]}
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)