140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Trie tree (does not have to use this data structure)

class Node: 
    def __init__(self, word=None): 
        self.children = {} 
        self.isleaf = False 
        self.word = word 

class Solution: 
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: 
        s = s 
        dummy = Node('') 
        for word in wordDict: 
            cur = dummy 
            for i, c in enumerate(word): 
                if c not in cur.children: 
                    cur.children[c] = Node() 
                cur = cur.children[c] 
                if i == len(word) - 1: 
                    cur.isleaf = True 
                    cur.word = word 
                    
        @lru_cache(None) 
        def wordBreakPartial(istart): 
            curnode = dummy 
            ans = [] 
            for i in range(istart, len(s)): 
                c = s[i] 
                if c in curnode.children: 
                    curnode = curnode.children[c] 
                    if curnode.isleaf: 
                        if i == len(s) - 1: 
                            ans.append(curnode.word) 
                        else: 
                            for sentence in wordBreakPartial(i + 1): 
                                ans.append(curnode.word + ' ' + sentence) 
                else: 
                    break 
            return ans 
        return wordBreakPartial(istart=0)