Word Break

mediumTests passed 2026-11-11v1.0.0
TC: O(N * W * L)|SC: O(N)
1D DPStringsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Define `dp[i] = True` iff prefix `s[:i]` can be segmented. Instead of checking every split `0..i`, probe each word `w` in `wordDict` backward from `i` (`dp[i - len(w)] and s[i-len(w):i] == w`) with a hash set or bounded lengths.

2. Complexity Bounds & Proof

For each prefix end `i in 1..N`, matches only existing dictionary words in `O(W * L)` or unique lengths `L`.

3. Minimal Idiomatic Code

def wordBreak(s: str, wordDict: list[str]) -> bool:
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for w in wordDict:
            if i >= len(w) and dp[i - len(w)] and s[i - len(w):i] == w:
                dp[i] = True
                break
    return dp[n]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Greedy prefix matching fails when a longer dictionary word hides a valid split (e.g. `"cars"` vs `["car","ca","rs"]`).
Follow-ups:- Word Break II adds memoized path reconstruction (or Trie + DP pruning) to enumerate all sentences.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Decode Ways (O(N))Word Ladder (O(N * L^2))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.