原題

給出一個(gè)字符串s和一個(gè)詞典，判斷字符串s是否可以被空格切分成一個(gè)或多個(gè)出現(xiàn)在字典中的單詞。

給出
s = "leetcode"
dict = ["leet","code"]
返回 true 因?yàn)?strong>"leetcode"可以被空格切分成"leet code"

解題思路

• 動(dòng)態(tài)規(guī)劃是一種解決問(wèn)題的思想 - 大規(guī)模問(wèn)題的結(jié)果，是由小規(guī)模問(wèn)題的結(jié)果運(yùn)算得來(lái)的
• 動(dòng)態(tài)規(guī)劃不等同于遞歸，動(dòng)態(tài)規(guī)劃思想可以由遞歸來(lái)實(shí)現(xiàn)
• DP初始化時(shí)一般要有個(gè)1或者true
• 本題屬于序列型動(dòng)態(tài)規(guī)劃 - Sequence DP
• cache[i]表示前i個(gè)字符能不能被dict完美劃分
• 判斷cache[i]，則需要遍歷0~i中是否存在一個(gè)j，使得cache[j]=true而且j+1~i存在于dict中
• 本題還有一個(gè)值得注意的地方，一定要考慮到單詞長(zhǎng)度是有上限的！，所以每次不需要遍歷0~i而是x~i(i-x為單詞最大長(zhǎng)度)

完整代碼

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