DSAPrep
Medium1-D DP

Word Break

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.

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

Example 1

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".

Example 2

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" can be segmented as "apple pen apple", reusing "apple".

Example 3

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.
View original on LeetCode ↗

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]

Trace for s = "leetcode", wordDict = ["leet","code"] (dp values shown as T/F):

T
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
1 / 9
comparingresultdiscarded

dp[0] = True: the empty prefix needs zero words.

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).