Word Break

MediumString DP · Prefix Reachability🧩 String DP LeetCode #139 ↗Updated Oct 30, 2026

Problem

You are given a string s and a list of words wordDict. Decide whether s can be cut into one or more pieces so that every piece is a dictionary word. Words may be reused any number of times.

Input"leetcode", [leet,code]Outputtrue

Input"applepenapple", [apple,pen]Outputtrue

Input"catsandog", [cats,dog,sand,and,cat]Outputfalse

1 ≤ |s| ≤ 300 · 1 ≤ |wordDict| ≤ 1000 · 1 ≤ |word| ≤ 20 · lowercase letters, distinct words

Try it yourself

Java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Whether the suffix starting at index i (or the prefix ending at i) can be segmented depends only on i — just n+1 distinct subproblems. Solve each once, and only try pieces no longer than the longest word.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForcePlain Recursion over Cut Points

Time O(2ⁿ)Space O(n)

From index start, try every end: if s[start..end) is a word, recurse on the rest. A string like "aaa…ab" with words a, aa, aaa explores every one of the 2^n-1 ways to cut it.

Java

public boolean wordBreak(String s, List<String> wordDict) {
    return canBreak(s, new HashSet<>(wordDict), 0);
}
private boolean canBreak(String s, Set<String> dict, int start) {
    if (start == s.length()) return true;
    for (int end = start + 1; end <= s.length(); end++) {
        if (dict.contains(s.substring(start, end)) && canBreak(s, dict, end)) return true;
    }
    return false;
}

Correct and tiny, but the same suffix is re-solved again and again.

BetterTop-Down Memoization

Time O(n³)Space O(n)

The answer for a suffix depends only on start, so cache it in a Boolean[] memo. Each of the n starts tries up to n ends, and each try builds/hashes a substring in O(n).

Java

private Boolean[] memo;

public boolean wordBreak(String s, List<String> wordDict) {
    memo = new Boolean[s.length()];
    return canBreak(s, new HashSet<>(wordDict), 0);
}
private boolean canBreak(String s, Set<String> dict, int start) {
    if (start == s.length()) return true;
    if (memo[start] != null) return memo[start];
    for (int end = start + 1; end <= s.length(); end++) {
        if (dict.contains(s.substring(start, end)) && canBreak(s, dict, end)) {
            return memo[start] = true;
        }
    }
    return memo[start] = false;
}

Polynomial, but still tries pieces far longer than any dictionary word.

OptimalBottom-Up DP, Pieces ≤ Longest Word

Time O(n·L²)Space O(n + m·L)

dp[i] = “prefix s[0..i) can be segmented”, with dp[0] = true. dp[end] is true if some reachable start has s[start..end) in the set. A piece longer than L (longest word) can never match, so only L starts are tried (m = number of words).

Java

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int maxLen = 0;
    for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
    int n = s.length();
    boolean[] dp = new boolean[n + 1]; // dp[i]: s[0..i) is segmentable
    dp[0] = true;
    for (int end = 1; end <= n; end++) {
        for (int start = end - 1; start >= Math.max(0, end - maxLen); start--) {
            if (dp[start] && dict.contains(s.substring(start, end))) {
                dp[end] = true;
                break;
            }
        }
    }
    return dp[n];
}

Dry run"leetcode", [leet,code] (dp[0..8])

s starte end changed

init
T
s
F

F

F

F

F

F

F

F

empty prefix ok
e=1..3
T

F

F

F

F

F

F

F

F

l, le, lee: no word
e=4
T
s
F

F

F

T
e
F

F

F

F

"leet" & dp[0]
e=5..7
T

F

F

F

T

F

F

F

F

no valid piece
e=8
T

F

F

F

T
s
F

F

F

T
e
"code" & dp[4] ✔

Iterative, no recursion depth, and with L ≤ 20 it is effectively linear.

Pro tip

For huge dictionaries, walk a Trie forward from each reachable start instead of hashing substrings.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Recursion over Cut Points	`O(2ⁿ)`	`O(n)`
Better	Top-Down Memoization	`O(n³)`	`O(n)`
Optimal	Bottom-Up DP, Pieces ≤ Longest Word	`O(n·L²)`	`O(n + m·L)`

Common pitfalls

Greedy “take the longest matching word” fails: "abcd", [ab,abc,cd] needs the shorter ab.
Using List.contains — O(m) per lookup; convert to a HashSet first.
Forgetting dp[0] = true (empty prefix) — nothing ever becomes reachable.

Interview tips

Show the recursion first, then point at the repeated suffixes to justify memoization.
Mention the max-word-length bound — it turns O(n³) into ~O(n·L²).
Follow-up Word Break II asks for all sentences — output can be exponential.

Pattern

Prefix-reachability DP → “can the string be split into valid pieces?” (dp[i] from dp[j] + valid s[j..i)).

My notes saved in this browser