[LeetCode] 140. Word Break II

Problem : https://leetcode.com/problems/word-break-ii/

Use memorization approach to cache the result of,  starting from position "start", whether it is possible to break string into words in dictionary.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDictSet = set(wordDict)
        result = []
        
        @lru_cache(maxsize = None)
        def backtracking(start):
            if start == len(s):
                return [[]]
            
            result = []
            for i in range(start, len(s)):
                tmp = s[start:i+1]
                if tmp in wordDictSet:
                    partials = backtracking(i+1)
                    for p in partials:
                        result.append([tmp] + p)
                    
            return result
        
        result = backtracking(0)
        
        return map(lambda x : " ".join(x), result)