LeetCode 139 [Word Break]

原题

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

给出
s = "leetcode"
dict = ["leet","code"]
返回 true 因为"leetcode"可以被空格切分成"leet code"

解题思路

• 动态规划是一种解决问题的思想 - 大规模问题的结果，是由小规模问题的结果运算得来的
• 动态规划不等同于递归，动态规划思想可以由递归来实现
• DP初始化时一般要有个1或者true
• 本题属于序列型动态规划 - Sequence DP
• cache[i]表示前i个字符能不能被dict完美划分
• 判断cache[i]，则需要遍历0~i中是否存在一个j，使得cache[j]=true而且j+1~i存在于dict中
• 本题还有一个值得注意的地方，一定要考虑到单词长度是有上限的！，所以每次不需要遍历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