Problem of The Day: Word Break

Problem Statement

leetcode problem link

Solution [Accepted]

from functools import lru_cache
from typing import List

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

        @lru_cache(maxsize=None)
        def dp(i):
            # Base case: empty string is always breakable
            if i < 0:
                return True

            # Try each word in the dictionary
            for word in wordDict:
                word_len = len(word)
                # Check if this word can end at position i
                if i >= word_len - 1:
                    # Check if substring matches the word
                    if s[i - word_len + 1:i + 1] == word:
                        # Check if the part before this word is breakable
                        if dp(i - word_len):
                            return True

            return False

        return dp(n - 1)

Other Approach [Accepted]

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        def dfs(start, s):
            if start >= len(s):
                return True

            if start in memo:
                return memo[start]

            result = False
            for word in wordDict:
                if s[start:].startswith(word):
                    if dfs(start + len(word), s):
                        result = True
                        break

            memo[start] = result
            return memo[start]

        memo = {}
        return dfs(0, s)

Editorial

Bottom-up Implementation

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * len(s)
        for i in range(len(s)):
            for word in wordDict:
                # Make sure to stay in bounds while checking criteria
                if i >= len(word) - 1 and (i == len(word) - 1 or dp[i - len(word)]):
                    if s[i - len(word) + 1 : i + 1] == word:
                        dp[i] = True
                        break

        return dp[-1]

Top-down Implementation

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

            return False

        return dp(len(s) - 1)