LeetCode 140. Word Break II

LeetCode 140

可以使用dfs的方法來查找，不斷的match prefix的部分，如果成功，那麼遞歸繼續，直到能match到字元串結束，如果不成功，那麼就增加prefix的部分繼續match。

增加一個優化就是，先考慮是否有足夠長的字元串可以用于match，如果不夠，可以快速結束。

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:        
        wordLets = set(''.join(wordDict))        
        stringLets = set(s)

        if stringLets - wordLets:
            return []        
        
        wordDict = set(wordDict)
        result = []

        def matchWord(s, wordDict, currentMatched, cstart, cend, result):
            if cstart == len(s):
                result.append(" ".join(currentMatched))
                return
            
            for iend in range(cend, len(s)+1):
                subs = s[cstart:iend]
                if subs in wordDict:
                    currentMatched.append(subs)
                    matchWord(s, wordDict, currentMatched, iend, iend+1, result)
                    currentMatched.pop(-1)
        matchWord(s, wordDict, [], 0, 1, result)
        return result