Dynamic Programming • Strings

Word Break

Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of dictionary words.

Try Interactive Simulator

Overview

This is a partitioning problem. We want to know if the string `s[0...i]` can be broken up into valid dictionary words.

The DP Array

`dp[i]` is a boolean indicating whether the prefix of length `i` is breakable. We use an array of size `N + 1`.

The Transition

To find if `dp[i]` is true, we test all possible split points `j` (from 0 to i-1). If `dp[j]` is true, AND the remaining substring `s[j...i]` is in the dictionary, then `dp[i]` is true!

The Early Exit

As soon as we find ONE valid `j` that makes `dp[i]` true, we can immediately `break` the inner loop and move on to the next `i`. We just need to know IF it's possible, not how many ways.

c

a

t

s

a

n

d

DP Array (Can segment up to length L?)

0

T

1

F

2

F

3

F

4

F

5

F

6

F

7

F

Code Tracker

:::

1let dp = new Array(s.length + 1).fill(false);

2dp[0] = true;

3let dict = new Set(wordDict);

4for (let i = 1; i <= s.length; i++) {

5 for (let j = 0; j < i; j++) {

6 if (dp[j] && dict.has(s.substring(j, i))) {

7 dp[i] = true;

8 break;

9 }

10 }

11}

12return dp[s.length];