MediumCan a string be split into dictionary words? Reachability DP over prefixes.
Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.
Walkthrough
try:
Can s be split into a sequence of dictionary words? dp[i] means the first i letters break cleanly.
dictleetcode
l
e
e
t
c
o
d
e
dp
F
0
F
1
F
2
F
3
F
4
F
5
F
6
F
7
F
8
s.slice(j, i)matched word / true
1
function wordBreak(s, wordDict) {
2
const words = new Set(wordDict);
3
const dp = Array(s.length + 1).fill(false);
◄
4
dp[0] = true;
5
for (let i = 1; i <= s.length; i++) {
6
for (let j = 0; j < i; j++) {
7
if (dp[j] && words.has(s.slice(j, i))) {
8
dp[i] = true;
9
break;
10
}
11
}
12
}
13
return dp[s.length];
14
}
step 0 / 48
line 3
dp[i] = can s[0..i) be broken?
dp[i] is true when the first i characters split cleanly into dictionary words.
Intuition
Think of positions 0..n as stepping stones. dp[i] = true means “the first i characters can be split cleanly”, i.e. position i is reachable.
dp[0] = true — the empty prefix needs no words. It is the launch pad for everything else.
Position i is reachable if there is some earlier reachable position j where the chunk s[j..i) is a dictionary word. So you look BACK from i over every split point j.
Once you find one working j you can stop early (break) — one valid split is all it takes. The answer is dp[n].
The algorithm
01Put the dictionary into a hash set for O(1) lookups.
02dp[0] = true; all other dp values start false.
03For each end i, scan every start j < i: if dp[j] is true and s[j..i) is a word, set dp[i] = true and break.