Word Break (LC 139)

Pattern: Dynamic Programming + HashSet
Difficulty: Medium
Key Concept: A string is breakable if some prefix is a dictionary word and the remainder is also breakable—so you reuse answers for suffixes.

Problem Statement

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: The same word may be reused multiple times in the segmentation.

Input: s (non-empty string), wordDict (list of non-empty strings, all lowercase).
Output: boolean.

Examples:

• s = "leetcode", wordDict = ["leet","code"] → true ("leet code").
• s = "applepenapple", wordDict = ["apple","pen"] → true.
• s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] → false.

---

1. Algorithm & Pseudocode

Brute force

1. Try every possible first word: for each end index j from 1 to n, check if s[0..j) is in the dictionary.
2. If yes, recursively solve the same problem for the suffix s[j..n).
3. If any choice leads to a full segmentation, return true; if none do, return false.
4. Without memoization this revisits the same suffixes exponentially.

Pseudocode (naive):

function canBreak(s, wordSet):
    if s is empty: return true
    for j from 1 to len(s):
        if s[0:j] in wordSet and canBreak(s[j:], wordSet):
            return true
    return false

Optimal

1. Put wordDict in a HashSet for O(1) lookups.
2. Let dp[i] mean: s[0..i) can be segmented (dp[0] = true for empty prefix).
3. For each i from 1 to n, for each j from 0 to i-1, if dp[j] is true and s[j..i) is in the set, set dp[i] = true and break inner loop.
4. Answer is dp[n].

Pseudocode (DP):

dp[0] = true
for i from 1 to n:
    dp[i] = false
    for j from 0 to i-1:
        if dp[j] and s[j:i] in wordSet:
            dp[i] = true
            break
return dp[n]

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force explodes: From the start you can pick many valid first words; each choice spawns the same subproblem on a shorter string. Many paths reach the same suffix (e.g. different ways to reach index k), so you redo work without memory.

Why DP works: dp[i] only depends on whether some earlier boundary j was reachable and the slice s[j..i) is a word. Once you know dp[j], you never need to re-derive how you got to j—only that the prefix up to j is breakable.

Why HashSet: Checking s.substring(j, i) membership must be O(1) on average; a list scan per check would multiply the DP cost.

---

3. The Dry Run

s = "leetcode", wordDict = {"leet", "code"} (indices 0-based, n = 8).

i	j	dp[j]	substring s[j..i)	in set?	dp[i] after
1	0	true	“l”	no	false
2	0	true	“le”	no	false
…	…	…	…	…	false through i=3
4	0	true	“leet”	yes	true
5	…	…	…	…	stays true once set
8	4	true	“code”	yes	true

Final: dp[8] = true.

---

4. Java Solution

Brute Force

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    // Naive recursion — exponential without memo
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        return dfs(s, 0, words);
    }

    private boolean dfs(String s, int start, Set<String> words) {
        if (start == s.length()) {
            return true;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String prefix = s.substring(start, end);
            if (words.contains(prefix) && dfs(s, end, words)) {
                return true;
            }
        }
        return false;
    }
}

Time: O(2^n) worst case (many splits). Space: O(n) recursion stack.

Optimal

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> words = new HashSet<>(wordDict);
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (!dp[j]) {
                    continue;
                }
                if (words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

Time: O(n^3) in worst case (two nested loops × substring cost O(n) in typical Java). Space: O(n) for dp plus O(m) for the set where m is dictionary size.

---

5. The “Java vs. Others” Edge

• substring(j, i) creates a new String; in a tight DP loop this adds overhead. Interview optimization: use trie or store words and match by scanning s with trie from j to avoid many substring objects (advanced).
• HashSet.contains is the natural Java choice; List.contains would be O(dict) per check.
• Bottom-up boolean[] avoids boxing vs Boolean[] or Map<Integer, Boolean> for memo.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute DFS	O(2^n) worst	O(n) stack	Overlapping subproblems without cache
DFS + memo	O(n^2) typical	O(n) memo + stack	Cache start → result
1D DP	O(n^3) with substring	O(n)	Simple; trie can improve string work
1D DP + trie	O(n^2) or better	O(n + dict)	Less substring allocation