Solutions

# DFS + memoization, bottom-up DP, Trie + bottom-up DP
# dp

# DFS + memoization - O(m * n * t) time, O(n) space
# w/o memoization O(n 2^n + m) time, O(n + m*t)
def wordBreak(s: str, wordDict: list[str]) -> bool:
    cache = { len(s): True } # base case

    def dfs(i: int) -> bool:
        if i in cache:
            return cache[i]

        for w in wordDict:
            if ((i + len(w)) <= len(s) and
                s[i : i + len(w)] == w):

                if dfs(i + len(w)):
                    return True

        cache[i] = False
        return False

    return dfs(0)

        
# Bottom-up DP - O(m * n * t) time, O(n) space
def wordBreak1(s: str, wordDict: list[str]) -> bool:
    # dp[i] means whether the substring s[i:] can be segmented
    dp = [False] * (len(s) + 1)
    dp[len(s)] = True

    for i in range(len(s) - 1, -1, -1):
        for w in wordDict:
            if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                dp[i] = dp[i + len(w)]
            if dp[i]: # break early if we know for that position it's True
                break

    return dp[0]


# Trie + Bottom-up DP
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, s, i, j):
        node = self.root
        for idx in range(i, j + 1):
            if s[idx] not in node.children:
                return False
            node = node.children[s[idx]]
        return node.is_word

class SolutionTrie:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        trie = Trie()
        for word in wordDict:
            trie.insert(word)

        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        t = 0
        for w in wordDict:
            t = max(t, len(w))

        for i in range(len(s), -1, -1):
            for j in range(i, min(len(s), i + t)):
                if trie.search(s, i, j):
                    dp[i] = dp[j + 1]
                    if dp[i]:
                        break

        return dp[0]