This problem is a pretty standard dynamic programming problem, where you start with a recursive/backtracking solution, memoize it and finally understand the pattern to come up with a bottom-up iterative approach. A challenge I face while solving this problem was understanding why memoization was needed because the given examples didn’t seem to need it. But, once I realized that each recursive call took n^2 time complexity it made sense because dynamic programming problems I solved before usually had constant time operations for each recursive call.

So, the approach I came up with was to go through each index of the string and check if the substring from the start to the index was in the wordDict, and then if it was we recurse on the other half. This approach is O(n^3+m) time and O(n) space, where n is the length of the string and m is the length of the wordDict. The other approach is to check if any word in the wordDict matches the first portion of the string and if it did we recurse the other half. The time complexity for this is O(n^2*m) and space is O(n).

The First Approach (my approach)

Recursive Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        memo = {"":True}
        def canBreak(s):
            if s not in memo:
                memo[s] = False
                for i in range(len(s)):
                    if s[i:] in wordDict and canBreak(s[:i]):
                        memo[s] = True
                        break
            return memo[s]
        return canBreak(s)

Iterative Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[-1] = True
        for idx in range(len(s)-1,-1,-1):
            for i in range(idx+1, len(s)+1):
                if s[idx:i] in wordDict and dp[i]:
                    dp[idx] = True
                    break
        return dp[0]

The Second Approach

Recursive Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = {"":True}
        def canBreak(s):
            if s not in memo:
                memo[s] = False
                for word in wordDict:
                    if s[:len(word)] == word and canBreak(s[len(word):]):
                        memo[s] = True
                        break
            return memo[s]
        return canBreak(s)

Iterative Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s)+1)
        dp[-1] = True
        for idx in reversed(range(len(s))):
            for word in wordDict:
                if s[idx:len(word)+idx] == word and dp[len(word)+idx]:
                    dp[idx] = True
                    break
        return dp[0]