单词拆分

Leetcode Link:

题目

解法一

暴力递归到记忆化搜索（不能转化为动态递归）

然而这个思路不好，有点乱

暴力递归

子问题是： 已知当前的字符串 strs，字典 wordDict，返回能不能拼出该字符串（True or False）

拿字典中的每个单词来试试，看看能不能把strs中开头的字母给match上 (可以画个树来考虑这个问题，是不重不漏的)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        return self.process(wordDict, s)
 
    def process(self, wordDict, strs):
        if strs == '':
            return True
         
        res = False 
        for word in wordDict:
	        # 看看字符串的开头是不是当前这个字典元素
            if strs.startswith(word): 
	            # 替换后进入下一个子问题
                res = res or self.process(wordDict, strs.replace(word, "", 1))
 
        return res

记忆化搜索

显然，这个问题存在了重复的调用 由于我们定义该子问题时，只和 strs 有关，所以基于目前这个子问题，就不能转化为 dp，但是可以用记忆化搜索，memo 是字典，strs 是key

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        self.memo = {}
        return self.process(wordDict, s)
 
    def process(self, wordDict, strs):
        if strs == '':
            return True
        
        if strs in self.memo:
            return self.memo[strs]
 
        res = False
        for word in wordDict:
            if strs.startswith(word):
                res =  res or self.process(wordDict, strs.replace(word, "", 1))
        self.memo[strs] = res
        return res

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系