LeetCode 140-単語分割II In Python
1150 ワード
この問題は前の単語の分割1思想と同じだが、実現はもっと複雑だ.この問題は分割できる単語を書くことを要求している.
問題:暴力の再帰タイムアウトを試した.前の問題のダイナミックな計画思想はこの問題の中で具体的な種類を書くことができません.しかし、記憶化する方法もある.ダイレクトコード
コード:
問題:暴力の再帰タイムアウトを試した.前の問題のダイナミックな計画思想はこの問題の中で具体的な種類を書くことができません.しかし、記憶化する方法もある.ダイレクトコード
コード:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
return self.findword(s,wordDict,{})
def findword(self,s,wordDict,m):
#m ,key s,value s ,
# m s,
if s in m:
return m[s]
# ,
if not s:
return 'ok'
res=[]
#
for i in wordDict:
if s[:len(i)]!=i:
continue
exres=self.findword(s[len(i):],wordDict,m)
# ok, , ,
# res
if exres=='ok':
res.append(i)
# s[len(i):]
elif exres:
for j in exres:
res.append(i+' '+j)
# [] , s[len(i):]
# elif not exres:
# pass
m[s]=res
return res