Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word.

word_break_2.py

"""
Input
s =
"pineapplepenapple"
wordDict =
["apple","pen","applepen","pine","pineapple"]
"""

# This works

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        res = []
        wordSet = set(wordDict)

        def backtrack(s, curr_word, res):
            if not s:
                res += [' '.join(curr_word)]
                return
            substr = ""
            for idx, char in enumerate(s):
                substr += char
                if substr in wordSet:
                    curr_word += [substr]
                    backtrack(s[idx+1:], curr_word, res)
                    curr_word.pop()

                        
        backtrack(s, [], res)
        return res

      
# So does this, but faster and better
import functools

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)

        @functools.cache
        def backtrack(s):
            if not s:
                return [""]
            
            substr = ""
            res = []
            for idx, char in enumerate(s):
                curr_word = []
                substr += char
                if substr in wordDict:
                    for rest_statement in backtrack(s[idx+1:]):
                        if rest_statement:
                            res += [f"{substr} {rest_statement}"]
                        else:
                            res += [substr]
            return res or []

        res = backtrack(s)
        return res