数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究Python 中的单词拆分 II
假设我们有一个非空字符串 `s` 和一个字典 `wordDict`，该字典包含一个非空单词列表，在 `s` 中添加空格以构建一个句子，其中每个单词都是有效的字典单词。我们必须找到所有此类可能的句子。对 "appleraincoat" 和字典 [“app”、“apple”、“rain”、“coat”、“raincoat”]
为了解决这个问题，我们将遵循以下步骤 -
创建一个 map memo
定义一个名为 solve 的方法，它将获取 string 和 wordDict
如果 `s` 为空，则返回空列表
如果 `s` 在 memo 中，则 -
返回 memo[s]
创建一个数组 ret
对于从 1 到 s 大小的 i
如果 `s` 从索引 0 到 i - 1 的子字符串出现在 wordDict 中，则
对于 solve(`s` 从 i 到末尾的子字符串，wordDict)
`p` := `s` 从索引 0 到 i - 1 的子字符串，与空格连接和 j，然后从左右两边清除多余的空格 -
将 p 插入 ret
memo[s] := ret
返回 memo[s]
示例
让我们查看以下实现以更好地理解 −
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']
更新于：26-May-2020
416 浏览
广告