Leetcode 139. 单词拆分

心路历程这道题的递推结构很好找就是如果匹配到了一个字符串的话那么就看剩下部分的字符串能不能完全匹配就行了。相比于动态规划问题这道题更像是一道递归问题。由于随着问题不断变小的过程中s的长度也在逐渐缩小可以把s的长度看作一个背包问题的capacity字典集合就是物品的候选集合那么整个问题其实就是一个完全背包问题的变形。状态以s[i]结尾的字符串其实就是输入问题的从头开始的子串动作候选集wordDict返回值能否全部在字典中找到注意的点1、这道题的边界条件其实只需要对i-1进行处理i0的部分的处理可以被归并到递归循环中2、注意所有候选集合的动作匹配上一个就行所以要在对候选动作遍历时用res res or dp(i - len(word))动态规划背包问题建议递归动态规划classSolution:defwordBreak(self,s:str,wordDict:List[str])-bool:cachedefdp(i):# 代表以i为结尾的字符串# if i 0: return s[0] in wordDictifi-1:returnTrue# 从len(word) i 1 转换来的resFalseforwordinwordDict:iflen(word)i1:continueifs[i1-len(word):i1]word:resresordp(i-len(word))returnresreturndp(len(s)-1)转换成数组动态规划fromtypingimportListclassSolution:defwordBreak(self,s:str,wordDict:List[str])-bool:nlen(s)# dp[i] 表示 s[0:i] 是否能被拆分i 是长度不是下标# dp[0] True 表示空串可以被拆分dp[False]*(n1)dp[0]True# 枚举每个可能的结束位置foriinrange(1,n1):# 尝试每个单词forwordinwordDict:mlen(word)ifmi:# 单词比当前前缀长跳过continue# 检查后缀是否匹配且前半部分可拆分ifs[i-m:i]wordanddp[i-m]:dp[i]Truebreak# 找到一个就行可以提前退出returndp[n]