LeetEye LeetEye
Medium 1D Dynamic Programming ~5 min

Word Break

1d-dp word-break

Problem

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.

Examples

Example 1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
"leetcode" = "leet" + "code"
Example 2
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
"applepenapple" = "apple" + "pen" + "apple"
Example 3
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Key Insight

dp[i] = can s[0:i] be segmented? Check all possible last words.

dp[i] = can s[0:i] be segmented? True if for any j < i, dp[j] is True AND s[j:i] is in dictionary.

How to Approach This Problem

Pattern Recognition: When you see keywords like word break 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 dp[i] represents:
Answer: Whether s[0:i] can be segmented
Boolean - can we successfully segment the first i characters?
2 dp[i] is True if:
Answer: For some j, dp[j] is True AND s[j:i] is in dictionary
If we can segment s[0:j], and s[j:i] is a word, then s[0:i] is segmentable.
3 dp[0] should be:
Answer: True
Empty string is "trivially" segmented. Needed for recurrence.
4 For dp[i], we check j from:
Answer: 0 to i-1
Try all possible "last word" lengths. Either order works, but forward is typical.
5 We can optimize by:
Answer: All of above
Set for O(1) lookup, limit j range by max word length, early exit.

Solution

def wordBreak(s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    
    # dp[i] = can s[0:i] be segmented?
    dp = [False] * (n + 1)
    dp[0] = True  # Empty string
    
    for i in range(1, n + 1):
        for j in range(i):
            # If s[0:j] can be segmented and s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

Complexity Analysis

Time O(n² × m)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye