Word Break

Let dp[i] be true if the prefix s[0:i] can be fully segmented into dictionary words. s[0:i] is segmentable exactly when there is some earlier cut point j < i where s[0:j] is already segmentable (dp[j] is true) and the remaining piece s[j:i] is itself a single dictionary word. Trying every valid j gives the recurrence, with dp[0] = true as the base case (the empty prefix needs zero words).

Top-Down Memoization

Time O(n²)Space O(n)

Recurse forward from each index: canBreak(i) asks whether the suffix s[i:] can be segmented, by trying every possible first word starting at i.

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        memo = {}
        def canBreak(i: int) -> bool:
            if i == n:
                return True
            if i in memo:
                return memo[i]
            for j in range(i + 1, n + 1):
                if s[i:j] in words and canBreak(j):
                    memo[i] = True
                    return True
            memo[i] = False
            return False
        return canBreak(0)

Without memoization the same suffix can be re-explored from many different paths, causing exponential blow-up. Memoizing collapses this to n distinct starting positions, each trying up to n split points with an O(1) (average) dictionary lookup → O(n²) time, O(n) space for the memo and recursion stack (a hash set lookup is used, not a full string-comparison scan).

Bottom-Up DP

OptimalTime O(n²)Space O(n)

Fill dp[0..n] left to right. dp[0] = True. For each i, check every earlier cut point j < i: if dp[j] is true and s[j:i] is a dictionary word, then dp[i] is true.

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

Watch the DP scan: for each right edge i, the algorithm only looks up windows s[j:i] whose cut j already has dp[j] = true, and a window that is a dictionary word turns dp[i] true.

String s

dp table

cut j—dp[j]—window—in dict—

wordDict

leetcode

1 / 13

comparingresultdiscarded

dp[0] = true: the empty prefix needs zero words. Play through to fill the table left to right.

For each of the n cells, up to n split points are tried, each with an O(1) (average) hash-set lookup → O(n²) time, O(n) space for the dp array (a hash set of the dictionary words is also kept, adding O(total word length) space).

Top-Down Memoization

Bottom-Up DP

More 1-D DP practice