def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
res = [False] * (len(s) + 1)
res[0] = True
for i in range(1, len(s) + 1):
cur = s[:i]
for length in range(1, i + 1):
sub = cur[-length:]
remain_length = i - length
if sub in wordDict:
if res[remain_length]:
res[i] = True
break
return res[len(s)]
140题,使用递归。这种要返回所有可能结果的题目,无法用动态规划解。
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
# 转为set(hashtable),效率更高
wordDict = set(wordDict)
return self.wordBreakHelper(s, wordDict, {})
def wordBreakHelper(self, s, wordDict, memory):
if s == '':
return ['']
# 如果memory中有结果,直接从memory中取值
if s in memory.keys():
return memory[s]
res = []
# s由前一部分sub和后一部分remain(数组)构成, 如果sub在字典中进行下一步骤
# 如果remain为[''](当s为''的返回值),temp_res由sub构成
# 如果remain不为空,temp_res由 sub + " " + remain中的元素 构成
# 当remian为空,也会调用for循环,不过remain内没有元素,直接pass
for i in range(1, len(s) + 1):
sub = s[:i]
if sub in wordDict:
remain = self.wordBreakHelper(s[i:], wordDict, memory)
if remain == ['']:
res.append(sub)
else:
# 如果remain为空进入到else内,但是不会进入循环
for item in remain:
res.append(sub + " " + item)
# 将结果加入到memory中,key为s
memory[s] = res
return res