Python中的Word Break II
为了解决这个问题，我们将遵循以下步骤-
创建一个映射备忘录
定义一个名为Solve的方法，它将使用字符串和wordDict
如果s为null，则返回空列表
如果在备忘录中，则-
返回备忘录
创建一个数组ret
对于范围1到s的i
对于solve中的j（从i到s的子字符串，wordDict）
p：=s的子串，从索引0到i–1，由空格和j连接，然后从左右清除多余的空间-
将p插入ret
如果在wordDict中存在从索引0到i–1的s的子字符串，则
备忘：=ret
返回备忘录
示例
让我们看下面的实现以更好地理解-
class Solution(object):
def wordBreak(self, s, wordDict):
self.memo = {}
wordDict = set(wordDict)
return self.solve(s,wordDict)
def solve(self,s, wordDict):
if not s:
return ['']
if s in self.memo:
return self.memo[s]
ret = []
for i in range(1,len(s)+1):
if s[:i] in wordDict:
for j in self.solve(s[i:],wordDict):
ret.append((s[:i] + " " + j).strip())
self.memo[s] = ret
return self.memo[s]
ob = Solution()print(ob.wordBreak("appleraincoat",["app","apple","rain","coat","rain coat"]))输入值
"appleraincoat" ["app","apple","rain","coat","raincoat"]
输出结果
['apple rain coat', 'apple raincoat']