Word Break

MediumAmazonGoogleMetaBloomberg

Problem

Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Intuition — the key insight

dp[i] = can we segment s[0..i-1]? dp[i] is true if there exists some j < i where dp[j] is true AND s[j..i-1] is in the dictionary. Build from dp[0] = true (empty prefix always valid).

Approach

1. DP array definition

dp[i] means s[0..i-1] can be segmented. dp[0] = true (empty string). dp[i] = any j in [0,i) where dp[j] is true AND s[j:i] is in wordSet.

2. Fill the table

For i from 1 to len(s): for j from 0 to i: if dp[j] and s[j:i] in wordSet: set dp[i] = true and break.

Complexity

Time

O(n² × m) where m = avg word length for substring check

Space

O(n + dict size)

O(n²) state pairs, each with O(m) string comparison. HashSet lookup is O(m) for string hashing.

Solution code

Python

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    wordSet = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty prefix
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break  # no need to check other j
    
    return dp[n]

Edge cases to remember

⚠Single char matching dictionary: works fine

⚠Word used multiple times: allowed, dp handles reuse naturally

⚠Empty string: dp[0] = true handles this

⚠No valid segmentation: dp[n] remains false

Hints

What pattern do you think this problem uses?