原題
給出一個(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ī)劃是一種解決問題的思想 - 大規(guī)模問題的結(jié)果，是由小規(guī)模問題的結(jié)果運(yùn)算得來的
- 動(dòng)態(tài)規(guī)劃不等同于遞歸峦树，動(dòng)態(tài)規(guī)劃思想可以由遞歸來實(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è)值得注意的地方，一定要考慮到單詞長度是有上限的董瞻！寞蚌，所以每次不需要遍歷
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
