資料結構
網路
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 瀏覽
廣告