139. Word Break

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

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] 能否切分