139. 单词拆分

https://leetcode-cn.com/problems/word-break

解法一：回溯

显然超时

解法二：dp

用布尔变量dp[i]表示i之前的串s[0:i]是否能被拆分，i从1到n-1一次遍历，j从0到i，检测s[j:i]是否存在于字典中。若dp[j]为True且s[j:i]存在于字典中，则dp[i]也为True

class Solution:
    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'bool':
        dp = [False] * (len(s)+1)
        dp[0] = True  #初始化，空串能被任意拆分
        for i in range(1, len(s)+1):
            for j in range(0, i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break  #得到一个i拆分即可，进入i+1
        return dp[len(s)]
                    

优化：

对于以上代码可以优化。每次并不需要从s[0]开始搜索。因为wordDict中的字符串长度是有限的。只需要从i-maxLen开始搜索就可以了。

class Solution:
    def wordBreak(self, s: 'str', wordDict: 'List[str]') -> 'bool':
        dp = [False] * (len(s)+1)
        dp[0] = True
        
        maxLen = 0
        for word in wordDict:
            maxLen = max(maxLen, len(word))
            
        for i in range(1, len(s)+1):
            for j in range(max(i-maxLen, 0), i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[len(s)]