---
title: "DP on strings (word break)"
url: https://algopath.pro/patterns/dp-strings
language: en
summary: "Cut the string at every position and ask whether that piece is valid. A table of reachable positions kills the repeats off."
updated: 2026-08-24
---

# DP on strings (word break)

Cut the string at every position and ask whether that piece is valid. A table of reachable positions kills the repeats off.

## 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.

- `dp[0] = true` Splitting leetcode with the words leet and code.
- `dp[1] to dp[3] = false` The pieces l, le and lee are not words.
- `dp[4] = true` leet is a word and dp[0] is true.
- `dp[5] to dp[7] = false` No word ends at any of those positions.
- `dp[8] = true` code follows dp[4]. The whole string splits.

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

- 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.

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

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

## 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.

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

## 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.

## JavaScript

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

## Python

```python
def word_break(s, word_dict):
    words = set(word_dict)
    ok = [False] * (len(s) + 1)
    ok[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[len(s)]
```

## PHP

```php
function wordBreak(string $s, array $wordDict): bool {
    $words = array_flip($wordDict);
    $n = strlen($s);
    $ok = array_fill(0, $n + 1, false);
    $ok[0] = true;
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($ok[$j] && isset($words[substr($s, $j, $i - $j)])) {
                $ok[$i] = true;
                break;
            }
        }
    }
    return $ok[$n];
}
```