139. 单词拆分

题目链接

解题思路：暴力递归+缓存，也就是自顶向下的动态规划。process(s, index, wordDict)，s[index..]后面的能被wordDict拼出来吗？使用一个for循环，尝试wordDict中的所有单词。然后加一个缓存表，就可以了

代码

class Solution:

    # s2是s[i...]的一部分吗？ 如果是，返回拼接到s的结束位置， 例如s[i, j]就是s2，则返回j + 1，否则返回-1
    def check(self, s: str, i: int, s2: str) -> int:
        if i + len(s2) > len(s):
            return -1
        for ch in s2:
            if ch != s[i]:
                return -1
            i += 1
        return i
        
    # 现在在凑s[index...]，能凑出来吗？
    def process(self, s: str, index: int, wordDict: List[str], dp: List[int]) -> bool:
        if index == len(s):
            return True
        if dp[index] != -1:
            return dp[index] == 1
        # 用哪个字符来凑？
        for str1 in wordDict:
            next_index = self.check(s, index, str1)
            if next_index != -1:
                next = self.process(s, next_index, wordDict, dp)
                if next:
                    dp[index] = True
                    return True
        dp[index] = False
        return False

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [-1 for _ in range(len(s))]
        return self.process(s, 0, wordDict, dp)