题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，确定 s 是否可以被空格分割为一个或多个在字典里出现的单词。你可以假设字典中无重复的单词。

例如，给出 s = "leetcode"， dict = ["leet", "code"]。

返回 true 因为 "leetcode" 可以被切分成 "leet code"。

更新 (2017/1/4):

wordDict 参数已被更改为字符串列表（而不是一组字符串）。请重新加载代码定义以获取最新更改。

我的解法——DP（AC）

dp[i]/[j]表示i到j是否在词典中 or i到j分割后是否在词典中。
复杂度O(n2)

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        length = len(s)
        dp = [[0 for j in range(length)] for i in range(length)]
        
        wordDict = set(wordDict)
        
        if(s[0] in wordDict):
            dp[0][0] = 1
        else:
            dp[0][0] = 0
        
        for i in range(length):
            for j in range(i):
                if(s[:j + 1] in wordDict or dp[0][j] == 1):
                    dp[0][j] = 1

                if(s[j + 1:i + 1] in wordDict or dp[j + 1][i] == 1):
                    dp[j + 1][i] = 1
                
                if(dp[0][j] == 1 and dp[j + 1][i] == 1):
                    dp[0][i] = 1
            if(s[:i + 1] in wordDict):  # 边界判定太蛋疼了
                dp[0][i] = 1

        print(dp)
        return bool(dp[0][length - 1])

最优解法——DP

本题属于序列型动态规划 - Sequence DP
dp[i]表示前i个字符能否进行Wordbreak。当求解dp[i]时，可利用已经求解的dp[i-1],dp[i-2]…dp[1],dp[0]进行求解。对于dp[n]的求解，我们可以将n个字符进行切分求解，分为前i个字符和后n-i个字符，i可以为（0,1,2,3,4…n-1)。假设i为1时，可根据dp[i]和后面的n-1个字符组成的单词是否在dict中来判断dp[n]，只要i（0,1,2,3,4…n-1)其中一种情况为真，则dp[n]为true，表示可以进行workbreak。
空间复杂度为O(n)
再优化：本题还有一个值得注意的地方，一定要考虑到单词长度是有上限的！，所以每次不需要遍历0~i而是x~i(i-x为单词最大长度)

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        if not s:
            return True
        if not wordDict:
            return False
        
        maxLength = self.getMaxLength(wordDict)
        cache = [False for i in range(len(s) + 1)]
        cache[0] = True
        
        for i in range(1, len(s) + 1):
            j = 1
            while j <= maxLength and j <= i:
                if not cache[i - j]:
                    j += 1
                    continue
                if s[i - j:i] in wordDict:
                    cache[i] = True
                    break
                j += 1
                
        return cache[len(s)]
                

    def getMaxLength(self, dict):
        maxLength = 0
        for word in dict:
            maxLength = max(len(word), maxLength)
        return maxLength