Word Break
Problem
Given a string s and a dictionary of words, return true if s can be split into a sequence of one or more dictionary words. Each word can be used any number of times.
Example 1
Input: s = "leetcode", dict = ["leet", "code"] Output: true
Example 2
Input: s = "catsandog", dict = ["cats", "dog", "sand", "and", "cat"] Output: false
Also asked as: Word break Problem · Word Break Problem using Backtracking
Test cases
Case 1
Input: "leetcode", ["leet","code"] Expected: true
Case 2
Input: "applepenapple", ["apple","pen"] Expected: true
Case 3
Input: "catsandog", ["cats","dog","sand","and","cat"] Expected: false
View solutionHide solution1 approach
1. DP over prefixes
Time O(n² · L)Space O(n)
dp[i] = can s[0..i) be segmented. dp[i] is true if some j<i has dp[j] true and s[j..i) is in the dictionary.
function wordBreak(s, wordDict) { const dict = new Set(wordDict); const dp = Array(s.length + 1).fill(false); dp[0] = true; for (let i = 1; i <= s.length; i++) { for (let j = i - 1; j >= 0; j--) { if (dp[j] && dict.has(s.slice(j, i))) { dp[i] = true; break; } } } return dp[s.length];}