Q46: Word Break (Dynamic Programming)
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into space-separated dictionary words.
DP String Segmentation Word Break
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true; // Base case: empty string
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
}
console.log(wordBreak('leetcode', ['leet', 'code'])); // true💡
dp[i] is true if there exists split index $j$ where dp[j] is true and substring s[j..i] is present in wordSet.Key Takeaways
- Boolean array
dp[i]represents if prefixs[0..i]can be segmented. - State transition:
dp[i] = dp[j] && wordDict.has(s[j..i])for $0 \le j < i$.
Knowledge Check
What does dp[i] = true signify in the Word Break dynamic programming array?