FAANGPrep Sprint
Word Break
Decide whether the string s can be cut, end to end, into pieces that each appear in a given list of dictionary words, where any word may be used more than once.
Examples
The cut at 4 reaches "leet", and "code" finishes it.
Dictionary words may be reused, so "apple" is used twice.
Both "cats" and "cat" start it, but neither leaves a remainder the dictionary can finish.
Problem Understanding
We need to check if the entire string can be built using dictionary words. Words can be reused.
Example: s = "leetcode", dict = ["leet", "code"]
- "leet" + "code" -> Valid
- Output:
true
Algorithm Strategy
Let dp[i] be true when the first i characters can be cut into dictionary words.
Recurrence: dp[i] is true if there is some j < i where
dp[j]is true — the firstjcharacters already segment, ands[j...i)is in the dictionary.
Base case: dp[0] = true. The empty prefix needs no words, and it is what the first real word stands on.
One working j settles the question, so the inner loop stops at the first one it finds.
Interactive Visualization
COLUMN i = THE FIRST i CHARACTERS · T = REACHABLE · OUTLINED = THE CUT POINT AND THE PIECE BEING TESTED
BASE CASE — THE EMPTY PREFIX IS REACHABLE
0
1
2
3
4
5
6
7
8
s
dp
reachable
1/9
testing
—
Answer
—
dictionary
The empty prefix needs no words, so dp[0] is true — every segmentation starts from here
Next
Can the first 1 character, "l", be cut into words? Try every cut point
string, then words
Column i is the verdict on the first i characters. When a cut point is tested, its cell and the letters of the piece between it and i light together — so dp[j] and s[j:i] in words can be read straight off the picture.
Try Example 3: "cats" and "cat" both start it, and neither leaves a remainder the dictionary can finish.