# Leetcode 139. Word Break

## 題解

### 字典樹 (Trie) TLE

class TrieNode:
    def __init__(self):
        self.nodes = {}
        self.end = False

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        node = TrieNode()

        def builder() -> None:
            nonlocal node
            for word in wordDict:
                cur = node
                for w in word:
                    if w not in cur.nodes:
                        cur.nodes[w] = TrieNode()
                    cur = cur.nodes[w]
                cur.end = True
        
        def finder(index: int) -> bool:
            nonlocal node
            if index == n:
                return True
            cur = node
            state = False
            for i in range(index,n):
                st = s[i]
                if st in cur.nodes:
                    cur = cur.nodes[st]
                    if cur.end:
                        state = state or finder(i+1)
                        if state:
                            break
                    if not cur.nodes:
                        break
                else:
                    break
            return state
        
        builder()
        return finder(0)

#### 記憶化字典樹 (AC)


class TrieNode:
    def __init__(self):
        self.nodes = {}
        self.end = False

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Time complexity: O(n^2)
        # Space compelxity: O(sn)
        n = len(s)
        node = TrieNode()
        failed = [False for i in range(n)]

        def builder() -> None:
            nonlocal node
            for word in wordDict:
                cur = node
                for w in word:
                    if w not in cur.nodes:
                        cur.nodes[w] = TrieNode()
                    cur = cur.nodes[w]
                cur.end = True
        
        def finder(index: int) -> bool:
            nonlocal node
            if index == n:
                return True
            if failed[index]:
                return False
            cur = node
            state = False
            for i in range(index,n):
                st = s[i]
                if st in cur.nodes:
                    cur = cur.nodes[st]
                    if cur.end:
                        state = state or finder(i+1)
                        if state:
                            break
                        else:
                            failed[i+1] = True
                    if not cur.nodes:
                        break
                else:
                    break
            return state
        
        builder()
        return finder(0)

#### DP


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Time complexity: O(n^2)
        # Space complexity: O(n)
        n = len(s)
        dp = [False for i in range(n+1)]
        dp[0] = True
        wordSet = set(wordDict)
        for i in range(1,n+1):
            for j in range(0,i):
                strs = s[j:i]
                if dp[j] and strs in wordSet:
                    dp[i] = True
                    break
        return dp[n]