Python 中的分词 II
pythonserver side programmingprogramming更新于 2026/1/15 10:20:17
假设我们有一个非空字符串 s 和一个名为 wordDict 的字典，这个字典包含一个非空单词列表，在 s 中添加空格以构造一个句子，其中每个单词都是有效的字典单词。我们必须找到所有这样的可能的句子。“appleraincoat”并且字典是 [“app”, “apple”, “rain”, “coat”, “raincoat”]
为了解决这个问题，我们将遵循以下步骤 −
创建一个地图备忘录
定义一个名为solve的方法，它将采用字符串和wordDict
如果s为空，则返回空列表
如果s在备忘录中，则 −
返回备忘录[s]
创建一个数组ret
对于i，范围为1到s的大小
如果 wordDict 中存在从索引 0 到 i – 1 的 s 子字符串，则
for j insolv(从 i 到 end 的 s 子字符串，wordDict)
p := 从索引 0 到 i – 1 的 s 子字符串，用空格和 j 连接，然后清除左侧和右侧的额外空格 −
将 p 插入到 ret 中
memo[s] := ret
return 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']
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
