Word Break (LeetCode 139)

The problem

You get a string s and a list of words wordDict. Return True if s can be cut into a sequence of one or more dictionary words (words may be reused), otherwise False.

Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: True

"leetcode" splits as "leet" + "code", and both pieces are in the dictionary.

How to think about it

Start with brute force. Try every prefix that is a word, then recursively break the rest. In the worst case (like s = "aaaa…ab" with words "a", "aa", "aaa") the number of ways to split explodes, so plain recursion is exponential. The same suffix gets re-checked from many different split histories.

The key insight: only prefixes matter. Let dp[i] mean “the first i characters can be segmented”. The last word in such a split covers some s[j:i], and everything before it, s[:j], must itself be segmentable. So dp[i] is true if there is some j < i with dp[j] true and s[j:i] in the dictionary. The base case is dp[0] = True (the empty prefix).

Compute left to right. Each dp[i] uses only smaller indices, so fill the array in order and stop checking j as soon as one split works. Putting the words in a set makes each lookup O(1) on average.

Which pattern is this? 1-D DP over prefixes. The tell is “can this string be built from pieces”: the state is a prefix length, and the transition tries every possible last piece.

Approach

1. Put the words in a set. Make dp of length len(s) + 1, with dp[0] = True and the rest False.
2. For each end i from 1 to len(s), for each split j from 0 to i - 1: if dp[j] and s[j:i] is a word, set dp[i] = True and stop.
3. Return dp[len(s)].

Solution

def word_break(s, wordDict):
    words = set(wordDict); dp = [True] + [False] * len(s)   # dp[i]: s[:i] can be segmented
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words: dp[i] = True; break   # s[:j] works, s[j:i] is a word
    return dp[len(s)]
# word_break("leetcode", ["leet","code"]) -> True

Dry run

On s = "leetcode", the entries that become True:

Final dp = [T, F, F, F, T, F, F, F, T], so the answer is True.

Complexity

• Time: O(n²) checks, O(n³) counting substring work. There are about n²/2 pairs (j, i), and each slice s[j:i] costs up to O(n) to build and hash. Limiting j to i - maxWordLength cuts this down.
• Space: O(n) for dp, plus the word set.

Edge cases and pitfalls

• Words can repeat: "aaaa" with ["aa"] is True.
• Greedy longest-match fails: "aaaaaaa" with ["aaaa", "aaa"] is True (4 + 3), but always taking the longest first can dead-end on other inputs.
• Forgetting dp[0] = True makes every answer False.
• Using the list for lookups makes each check O(words); convert to a set first.

Related problems

• Decode Ways (LeetCode 91): the same prefix DP, counting splits into valid 1- or 2-digit codes.
• Coin Change (LeetCode 322): “try every last piece” again, with coins instead of words.
• Implement Trie (LeetCode 208): a trie can replace the set to scan matching words from each start.