原题
给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
给出
s = "leetcode"
- dict = ["leet","code"]
返回 True 因为"leetcode"可以被空格切分成"leet code"- dict = ["leet","code","3"]
返回 True- dict = ["leet","cod","g"]
返回 False
解题思路
- 1、DP初始化时一般要有个1或者true
- 2、本题属于序列型动态规划 - Sequence DP
- f[i]表示前i个字符能不能被dict完美划分
判断f[i]，则需要遍历0i中是否存在一个j，使得f[j]=true而且j+1i存在于dict中- 本题还有一个值得注意的地方，一定要考虑到单词长度是有上限的！，所以每次不需要遍历0i而是xi(i-x为单词最大长度)
def getMaxLength(self, dict):
maxLength = 0
for word in dict:
maxLength = max(len(word), maxLength)
return maxLength
def wordBreak(self, s, dict):
n = len(s)
if n == 0:
return True
if len(dict) == 0 :
return False
maxLength = self.getMaxLength(dict)
f = [False] * (n + 1) # 前i个字符是否可以被切分
f[0] = True
for i in range(1, n + 1): # 前i个字符，枚举j（j小于i）
j = 1
while j <= i and j <= maxLength:
if f[i - j] == False:
j += 1
continue
if s[i - j:i] in dict:
f[i] = True
break
j += 1
return f[n]
