139. Word Break

Difficulty: Medium

https://leetcode.com/problems/word-break/

This is a typical DP problem.

class Solution:
    def __init__(self):
        self.M = set()

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # n = len(s)
        # if n == 0:
        #     return True
        # for i in range(n):
        #     if s[:i + 1] in wordDict:
        #         if self.wordBreak(s[i + 1:], wordDict):
        #             return True
        # return False
        
        # Recursion with Memoization
        # memo = [-1 for i in range(len(s))]
        
        # def dp(i: int) -> bool:
        #     if i < 0:
        #         return True
        #     if memo[i] != -1:
        #         return memo[i] == 1
        #     for word in wordDict:
        #         size = len(word)
        #         if i - size + 1 < 0:
        #             continue
        #         if s[i - size + 1:i + 1] == word and dp(i - size):
        #             memo[i] = 1
        #             return True
        #     memo[i] = 0
        #     return False
        # return dp(len(s) - 1)

        # Bottom Up DP
        # dp(i) means word can break up to index i
        # n = len(s)
        # memo = [False for _ in range(n)]
        # for i in range(n):
        #     for word in wordDict:
        #         w_len = len(word)
        #         if i < w_len - 1:
        #             continue
        #         if i == w_len - 1 or memo[i - w_len]:
        #             if s[i - w_len + 1:i+1] == word:
        #                 memo[i] = True
        # return memo[-1]

        # Bottom up DP 2
        n = len(s)
        words = set(wordDict)
        memo = [False] * (n + 1)
        memo[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if memo[j] and s[j:i] in words:
                    memo[i] = True
                    break
        return memo[-1]

There is a special solution: Trie Optimization