Leetcode: 140. Word Break II

Can we use brute-force to solve the problem? Generate all possible answers using a Trie to optimize the search for the current word. Time and space complexity are \(2^n\).

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

        root = {}
        for w in wordDict:
            node = root
            for c in w:
                node.setdefault(c, {})
                node = node[c]
            node["$"] = w

        def bt(i, cur):
            nonlocal ans
            if i == len(s):
                ans.append(cur)
            node = root
            while i < len(s) and s[i] in node:
                node = node[s[i]]
                i += 1
                if "$" in node:
                    bt(i, cur + (" " if cur else "") + node["$"])

        bt(0, "")
        return ans