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