Word Break

Problem. Given a string $s$ and a dictionary, can $s$ be segmented into a sequence of dictionary words? And: how many ways, or what are they?

The DP — $O(n^2)$ (with $O(1)$ lookup)

$dp[i]={\bigvee }_{j<i}(dp[j]\wedge s[j..i)\in D).$

bool wordBreak(const string& s, const unordered_set<string>& dict) {
    int n = s.size(), maxLen = 0;
    for (auto& w : dict) maxLen = max(maxLen, (int)w.size());
 
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = max(0, i - maxLen); j < i; j++)
            if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; }
    return dp[n];
}

Bounding the inner loop by the longest dictionary word is the essential optimisation: $O(n\cdot L)$ substring lookups instead of $O(n^2)$.

With a trie — no substring construction

s.substr allocates a string per check, which dominates the runtime. A trie walk avoids it entirely:

for (int i = 0; i < n; i++) {
    if (!dp[i]) continue;
    int v = 0;
    for (int j = i; j < n; j++) {
        v = trie.nxt[v][s[j] - 'a'];
        if (v == -1) break;                          // no dictionary word continues
        if (trie.isEnd[v]) dp[j + 1] = true;
    }
}

$O(n^2)$ worst case, but the early break makes it near-linear on real dictionaries. This is the version to write.

The variants

Variant	Change
Can it be segmented?	boolean DP
Count the segmentations	dp[i] += dp[j] — beware of exponential counts, take mod
Output all segmentations	DFS with memoization; the output can be exponential
Output one segmentation	store a from[i] pointer and walk back
Minimum number of words	dp[i] = min(dp[j] + 1)
Maximum total word value	dp[i] = max(dp[j] + value)
Allow at most $k$ unknown characters	add a dimension
Dictionary given as a trie	the walk above
Words may be reused	already allowed
Each word at most once	NP-hard in general

Enumerating all segmentations

The number of segmentations can be exponential ("aaaa...a" with dictionary {a, aa}). Memoised DFS returning a list of strings will blow up on such inputs. Count them with a DP instead, and only enumerate when the problem bounds the output.

Aho-Corasick for many patterns

When the dictionary is large, build an Aho-Corasick automaton and run $s$ through it once. At each position, the suffix-link chain gives every dictionary word ending there:

int state = 0;
for (int i = 0; i < n; i++) {
    state = aut[state][s[i] - 'a'];
    for (int v = state; v; v = wordLink[v])          // words ending at i
        dp[i + 1] = dp[i + 1] || dp[i + 1 - len[v]];
}

$O(n+\sum |w|+\text{matches})$ — the right approach when the dictionary has $10^5$ words.

Related string DPs

Problem	Recurrence shape
Word break	$dp[i]$ from all valid $dp[j]$
Palindrome partitioning (min cuts)	$dp[i]=\min (dp[j]+1)$ over palindromic $s[j..i)$
Decode ways (digits to letters)	$dp[i]$ from $dp[i-1]$ and $dp[i-2]$
Concatenated words	word break with a length constraint
Text justification	$dp[i]=\min (dp[j]+\text{badness}(j,i))$ — Monge, so Knuth applies
Segment into $k$ parts	add a dimension

Text justification (Knuth-Plass line breaking) is the same shape with a convex cost, which is why SMAWK and D&C DP apply to it — the classical example of those optimisations.

Why it is worth knowing

It is the canonical “prefix DP over a string with a validity predicate”. Once you recognise that shape — dp[i] depends on all dp[j] where s[j..i) is valid — a large family of segmentation, partitioning and parsing problems becomes routine, and the only remaining question is how fast you can test the predicate.

See also: String DP · Trie · Aho-Corasick