DP on strings (word break)

O(n^2)

A boolean list ok[i] marks whether the first i characters split cleanly into dictionary words. ok[0] starts true, and ok[i] becomes true the moment some earlier ok[j] is true and the chunk between j and i is a real word.

Signals

can the string be split into dictionary wordssegment a string using a word listboolean reachable at each cut positionglued text needs word boundaries

Template

function wordBreak(s, wordDict) {
    const words = new Set(wordDict);
    const ok = new Array(s.length + 1).fill(false);
    ok[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (ok[j] && words.has(s.slice(j, i))) {
                ok[i] = true;
                break;
            }
        }
    }
    return ok[s.length];
}

Looks similar, isn't

DP on subsequences: Subsequence DP (LIS/LCS/edit distance) tracks the longest kept run across one or two sequences. Word break is a plain boolean over cut positions in ONE string: ok[i] just asks whether the first i letters split cleanly into dictionary words, with no longest common run to track.

string length n up to ~300..1000, checking every earlier cut point against a dictionary -> O(n^2) with O(1) dictionary lookups via a Set/hash.

Learn this pattern