139. Word Break

// 问题：长为 [0, i) (最初为0 - n)的字符串在不在wordDict中
// 子问题：[0, j)的字符串在不在wordDict中，[j, i)的字符串在不在wordDict中或能被wordDict中的word组合
// 枚举j
var wordBreak = function (s, wordDict) {
  const n = s.length
  const words = new Set(wordDict)
  // 0 - i 的子串在不在wordDict里
  const dfs = (i) => {
    if (i === 0) {
      return true
    }
    for (let j = i - 1; j >= 0; j--) {
      const word1 = s.slice(j, i)
      if (words.has(word1) && dfs(j)) {
        return true
      }
    }
    return false
  }
  return dfs(n)
}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        # i 表示 (0, i]
        @cache
        def dfs(i):
            if i == -1:
                # 这里返回True
                return True
            # [j, i]
            for j in range(i+1):
                if s[j:i+1] in wordDict and dfs(j-1):
                    return True
            return False
        return dfs(n)

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        n = len(s)
        word = set(wordDict)
        f = [False] * (n + 1)   # f[i] 表示前缀 s[:i] 能否切分 (i ∈ [0..n])
        f[0] = True             # f[0] = True 代表空串可切分

        # 外层循环：i 表示前缀长度，范围 [1..n]
        for i in range(1, n + 1):
            # 内层循环：j 表示最后一刀的位置，范围 [0..i-1]
            # 切分点：把 s[:i] 拆成 s[:j] + s[j:i]
            for j in range(i):
                # 如果前缀 s[:j] 可切分，且 s[j:i] 在字典中
                if f[j] and s[j:i] in word:
                    f[i] = True
                    break       # 找到一种切分即可，不必继续
        return f[n]             # f[n] 表示整个字符串 s[:n] 能否切分