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