LC 0140 [H] Word Break II - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=uR3RElKnrkU&ab_channel=anotherdigitalnomad

pine -> (all other substrs)
pine -> apple -> (all other substrs)
pine -> apple -> pen -> (all other substrs)
pine -> apple -> pen -> apple -> (all other substrs) ''

pine -> applepen -> (all other substrs)
pine -> applepen -> apple -> (all other substrs) ''

pineapple -> (all other substrs)
pineapple -> pen -> (all other substrs)
pineapple -> pen -> apple -> (all other substrs) ''
class Solution(object):
    def wordBreak(self, s, wordDict):
        @cache
        def branch(s): # DFS word break
            sentences = []
            for word in wordDict:
                if s.startswith(word):
                    if len(word) == len(s): # ...dog == dog, it'll always end in a dict word
                        sentences.append(word)
                    else:
                        suffix = s[len(word):]
                        suffix_sentences = branch(suffix)
                        for sentence in suffix_sentences:
                            sentences.append(word + ' ' + sentence)
            return sentences
        
        if not s: return []
        return branch(s)
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        s_to_sentences = {}
        
        def dp(s):
            if s in s_to_sentences: # check if we already broke this word into sentences
                return s_to_sentences[s]
            
            sentences = []
            
            period = '' # if we used . instead, have to replace it later when adding the reuslt
        
            # base case
            if not s:
                sentences.append(period)
                return sentences
            
            # break str apart and append the substrings to the first word(s)
            else:
                for word in wordDict: # cat
                    if s.startswith(word): # catsandog, cat
                        suffix = s[len(word):]
                        suffix_sentences = dp(suffix) # sanddog, compute the word break for the rest of the word
                        for sentence in suffix_sentences:
                            space_between = ' ' if sentence != period else '' # 'cats _' vs. 'cats_and_dog.'
                            sentences.append(word + space_between + sentence)
    
            s_to_sentences[s] = sentences # store the word break we were able to get
            return sentences
            
        return dp(s)