140. Word Break II

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        def WB(s):
            if not s:
                return [[]]
            if s in memo:
                return memo[s]
            for i in range(len(s)):
                word = s[:i+1]
                if word in wordDict:
                    for subseq in WB(s[i+1:]):
                        memo[s].append([word] + subseq)
            return memo[s]
        n = len(s)
        memo = defaultdict(list)
        result = WB(s)
        return [" ".join(i) for i in result]

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        return self.helper(s, wordDict, {})
    def helper(self, s, wordDict, memo):
        if s in memo: return memo[s]
        if not s: return []
        res = []
        for word in wordDict:
            #if not s.startswith(word):
            #    continue
            if word != s[:len(word)]:
                continue
            if len(word) == len(s):
                res.append(word)
            else:
                resultOfTheRest = self.helper(s[len(word):], wordDict, memo)
                for item in resultOfTheRest:
                    item = word + ' ' + item
                    res.append(item)
        memo[s] = res
        return res