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.

Sources: Wikipedia: Dynamic programming

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

function wordBreak(s: string, wordDict: string[]): boolean {
    const words = new Set(wordDict);
    const ok = new Array<boolean>(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];
}

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)]

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

    public static boolean wordBreak(String s, String[] wordDict) {
        Set<String> words = new HashSet<>(Arrays.asList(wordDict));
        boolean[] ok = new boolean[s.length() + 1];
        ok[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (ok[j] && words.contains(s.substring(j, i))) {
                    ok[i] = true;
                    break;
                }
            }
        }
        return ok[s.length()];
    }

    public static bool WordBreak(string s, string[] wordDict) {
        var words = new HashSet<string>(wordDict);
        var ok = new bool[s.Length + 1];
        ok[0] = true;
        for (int i = 1; i <= s.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (ok[j] && words.Contains(s.Substring(j, i - j))) {
                    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)?

Use DP on strings (word break) when the problem statement says “can the string be split into dictionary words”, “segment a string using a word list” or “boolean reachable at each cut position”. A solution built on it usually runs in O(n^2).

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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

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

DP on strings (word break) is most often confused with DP on subsequences (LIS / LCS / edit distance), Trie (prefix tree), Backtracking and Hash set / map.

• 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)?

Interview problems solved with DP on strings (word break) include Word break, Word break II, Palindrome partitioning II, Longest palindromic substring, Concatenated words, Extra characters in a string and Decode ways.

• 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)?

The target complexity of DP on strings (word break) is O(n2).

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