Word Break

Difficulty: Medium

Problem

Decide whether the string s can be cut into one or more pieces so that every piece is a word from the list wordDict. The pieces must cover all of s, appear in order, and any dictionary word may be reused as often as needed. Return true if such a split exists and false otherwise. Beware of inputs where partial attempts look promising from both ends yet always strand some unusable letters.

Example

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" splits as "leet" + "code": every character covered, both pieces straight from the dictionary.

Brute-force approach

No separate brute-force phase: the exponential recursive splitter IS Step 1 of the guided walkthrough, where it gets diagnosed and upgraded into the memo and then the boolean table.

Optimal approach

Key insight: Every segmentation ends with some final word. dp[i] asks: is there ANY split point j where the front part is already breakable and the back part s[j:i] is a word? One yes is enough, that's OR.

Build a boolean table over prefixes: dp[i] = True when the first i characters split cleanly into dictionary words. Each prefix auditions every split point j as the start of its FINAL word, dp[j] True AND s[j:i] in the word set flips dp[i] True, and dp[n] answers for the whole string.

Steps

Define the state: dp[i] = True if the first i characters can be split into dictionary words
Seed dp[0] = True (the empty prefix) and pour wordDict into a hash set
For each prefix end i from 1 to n, try every split point j < i
Flip dp[i] True the moment dp[j] is True AND s[j:i] is in the set, then break, one witness suffices
Return dp[n]: the verdict for the whole string

Time complexity: O(n² × average word check) · Space complexity: O(n) + dictionary set

Pseudocode

function wordBreak(s, wordDict):
    words = hashSet(wordDict)          // O(1) membership
    dp = array of size (length(s) + 1), filled with False
    dp[____] = True                    // the empty prefix: the anchor
    
    for i from 1 to length(s):
        for j from 0 to i - 1:
            if ____ is True and s[j..i] is in ____:
                dp[i] = True
                break                  // one witness is enough
    
    return ____

Hints

Before any word is placed, exactly one prefix already counts as 'fully segmented', the empty one. Which slot records that free fact?
If s[j..i] is the segmentation's FINAL word, the first j characters must already be breakable on their own. Which table slot certifies the front part?
The back part must be a real word. Which structure answers 'is this string in the dictionary?' in O(1) average time?
The original question is 'can the WHOLE string be segmented?'. Which slot holds the verdict for the full-length prefix?

Complexity questions

The Step-1 recursion (no memo) on s = "aaaa...ab" with words {a, aa, aaa}, how does it scale?

Exponential: every way to slice the a-run is explored, the same suffixes re-solved along countless peel sequences, and the final b guarantees every route fails only after the whole tree is walked. Each call can branch up to three ways (peel a, aa, or aaa), depth up to n, an exponential tree. The cruelty of the adversary is that no path succeeds, so nothing short-circuits: every slicing of the a-run gets its turn. Yet there are only n + 1 distinct suffixes underneath it all. That gap between tree size and state count is exactly the memo's opening.

And the tabulated solution: what's the honest accounting?

O(n²) split points. Every prefix end i tries up to i split points j, each an O(1)-amortized hash-set lookup. Fine print: building and hashing the slice s[j:i] adds a length factor (capping j-i by the longest word length tames it). Roughly n²/2 (i, j) pairs, each asking the set one membership question, O(n²) checks. The strict bill notes that s[j:i] must be sliced and hashed, which costs up to the substring's length; the common interview answer is 'O(n²) with a substring factor', and bounding the inner loop by the longest dictionary word is the standard tightening. Either way: polynomial, versus Step 1's exponential.

How much space does the tabulated solution use?

O(n) for the dp row, plus the hash set holding the dictionary (proportional to the total characters across all words); the memo version pays the same plus recursion stack. One boolean per prefix: n + 1 slots. The set is a real cost too, it stores every dictionary word, but it's usually counted separately as 'the dictionary.' No rolling-variable squeeze here: a final word can reach back arbitrarily far, so dp[i] may consult ANY earlier slot; the whole row stays alive. Compare House Robber, whose reach of 2 shrank the table to two variables.

Word Break II asks you to return ALL valid segmentations (as sentences), not just true/false. What changes?

The species of the answer: feasibility → enumeration. Each state now stores the LIST of sentences for its suffix, built by memoized DFS, and since a string can have exponentially many segmentations, the output itself can dwarf any polynomial budget. The skeleton survives (same last-word split, same subproblems) but the boolean 'can it?' becomes 'give me every way,' so each memo page holds a list of sentences instead of a bit. The DP still prunes dead prefixes (a False region produces empty lists cheaply), but when the answer genuinely has exponentially many sentences, no algorithm outruns its own output. Feasibility, counting, optimizing, enumerating: the question type sets the state type.

Check your understanding of Word Break

What counts as a valid segmentation?

The WHOLE string is split into dictionary words, in order, with words reusable any number of times. All three distractors are real bugs people write. Every character must be consumed (no leftovers), the characters keep their order (no rearranging), and the dictionary is a menu, not an inventory, "applepenapple" with ["apple","pen"] is true precisely because "apple" gets used twice.

Greedy: 'always take the LONGEST matching word first.' On s = "cars" with dictionary ["car","ca","rs"], what happens?

Greedy grabs "car", leaving "s": a dead end. The valid split is "ca" + "rs", which greedy never sees because it committed to the longest first word. The sin is COMMITMENT: the longest first word is not necessarily the first word of a valid segmentation. "cars" = "ca" + "rs" works, but longest-first dies holding "s". "catsandog" shows the same disease at scale, "cats" leaves "andog", "cat" leaves "sandog", and you must explore BOTH to know the truth. Only trying every split is safe; DP's job is making that affordable.

What's the state sentence: the meaning of one table slot dp[i]?

dp[i] = TRUE if the first i characters of s can be fully segmented into dictionary words, with dp[0] = True for the empty prefix. The state turns BOOLEAN, that's the feasibility signature. One slot per prefix length, answering yes/no: 'are these first i characters breakable?' dp[0] covers the zero-character prefix, which needs no words at all and is therefore trivially True. Counting would store numbers; optimizing would store bests; feasibility stores verdicts.

The recurrence: what case split defines dp[i]?

Split on the LAST word: the segmentation's final word is s[j:i] for some j, so dp[i] needs dp[j] True AND s[j:i] in the dictionary. Dp[i] = OR over all split points j. Stand at prefix i and ask what the LAST word was. It's s[j:i] for SOME j. We don't know which, so we try them all. Each candidate needs two things: the front part already breakable (dp[j]) and the back part a real word. AND joins the two halves of one candidate; OR joins the candidates. One workable split is all a yes/no question needs.

Why does dp[0] = True matter so much?

It's the anchor: a segmentation's very FIRST word s[0:i] has nothing before it, so its check reads dp[0] AND s[0:i] in dict. Seed dp[0] False and no slot can ever become True. Trace "leetcode": dp[4] flips True via dp[0] AND "leet" in dict. If dp[0] were False, that check fails, dp[4] stays False, and everything downstream starves. The whole row is False forever. The empty prefix being 'already segmented' (with zero words) is the one free fact the entire table grows from, exactly like dp[0] = 0 seeded Coin Change.