原题
给出一个字符串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
