DP on strings (word break)

How does DP on strings (word break) work?

State i means the first i characters can be split. State zero is true by definition.

For each position i, look back at every earlier position j. The piece between them is the candidate word.

The split works when state j is true and that piece is a word. Then state i is true as well.

One working j is enough. Stop the inner loop the moment you find it.

The answer is the last state. Nothing beyond position n exists.

Each position is decided exactly once. That is what turns exponential branching into a table.

1. dp[0] = trueSplitting leetcode with the words leet and code.
2. dp[1] to dp[3] = falseThe pieces l, le and lee are not words.
3. dp[4] = trueleet is a word and dp[0] is true.
4. dp[5] to dp[7] = falseNo word ends at any of those positions.
5. dp[8] = truecode follows dp[4]. The whole string splits.

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];
}

A worked example of DP on strings (word break)

Fewest cuts into palindromes

Cut a string into pieces that are all palindromes. Return the fewest cuts needed.

A single character already counts as a palindrome.

First mark every pair of positions that spans a palindrome.

Then state i is the fewest cuts for the first i characters. A palindromic tail costs one cut more.

function minCut(s) {
    const n = s.length;
    const isPal = Array.from({ length: n }, () => new Array(n).fill(false));

    for (let end = 0; end < n; end++) {
        for (let start = end; start >= 0; start--) {
            // the inside is already decided, because end - start only shrinks
            if (s[start] === s[end] && (end - start < 2 || isPal[start + 1][end - 1])) {
                isPal[start][end] = true;
            }
        }
    }

    const cuts = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) cuts[i] = i - 1; // cuts[0] is -1, so a whole palindrome costs 0

    for (let end = 0; end < n; end++) {
        for (let start = 0; start <= end; start++) {
            if (isPal[start][end]) {
                cuts[end + 1] = Math.min(cuts[end + 1], cuts[start] + 1);
            }
        }
    }

    return cuts[n];
}

When should you use DP on strings (word break)?

These phrases in a problem statement point here:

• •can the string be split into dictionary words
• •segment a string using a word list
• •boolean reachable at each cut position
• •glued text needs word boundaries

What is DP on strings (word break) confused with?

• DP on subsequences (LIS / LCS / edit distance): That lines up two separate sequences. This one splits a single string.
• Trie (prefix tree): A trie makes the dictionary lookup fast. The splitting logic above it stays the same.
• Backtracking: Backtracking lists every valid split. The table only answers whether one exists.
• Hash set / map: The dictionary is usually a set. The table is what stops a suffix being retried.

Common mistakes with DP on strings (word break)

• Rebuilding the substring every step

  Slicing inside the loop copies characters each time. Compare positions, or walk a trie.

• Looping the wrong way for palindromes

  The inside has to be decided before the outside. Grow by length, or walk the start backwards.

• Forgetting the empty prefix

  State zero is what lets the first word begin a split. Without it nothing is ever true.

• Listing every split when one is enough

  Word break asks only yes or no. Enumerating the splits is exponential.

Which interview problems use DP on strings (word break)?

• Word break: Whether the string can be split at all.
• Word break II: Every valid split, so backtracking comes back.
• Palindrome partitioning II: The fewest cuts, not the partitions themselves.
• Longest palindromic substring: The same palindrome table, read differently.
• Concatenated words: Each word is split using all of the others.
• Extra characters in a string: The cost of whatever letters are left over.
• Decode ways: One digit or two, over a fixed alphabet.

What is the time and space complexity of DP on strings (word break)?

O(n^2)

n characters with words up to m give O(nm). A set or a trie keeps the lookup near O(1).