139. 单词拆分

[Geekhyt]

原题链接

状态定义

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] 是否出现在字典中。

状态转移方程需要满足：

1. dp[j] 为真
2. 检查 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)