139. Word Break

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/word-break
• topics: Dynamic Programming

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Recursion + Cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        @cache
        def search(remainder):
            if not remainder:
                return True
            for i in range(len(remainder)+1):
                if remainder[0:i] in words and search(remainder[i:]):
                    return True
            return False
 
        return search(s)

Dynamic Programming Bottom Up

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        max_len = max(len(x) for x in wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True
 
        for i in range(len(dp)):
            for j in range(max(0, i-max_len), i):
                if not dp[j]:
                    continue
                elif s[j:i] in words:
                    dp[i] = True
                    break
 
        return dp[-1]

Dynamic Programming Top Down + Cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @cache
        def dp(i):
            if i < 0:
                return True
 
            for word in wordDict:
                if s[i - len(word) + 1 : i + 1] == word and dp(i - len(word)):
                    return True
 
            return False
 
        return dp(len(s) - 1)