Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Constraints:
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 5000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of lowercase English letters.
- 0 <= i <= wordDict.length - 1
Examples:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" can be segmented into "leet" and "code".
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" can be segmented into "apple", "pen", and "apple".
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: There is no way to segment "catsandog" into words in the dictionary.
Solutions
Dynamic Programming
The dynamic programming approach involves creating a boolean array dp where dp[i] is true if the substring s[0..i] can be segmented into words in the dictionary. We initialize dp[0] to true and then iterate over the string, checking for each substring if it can be segmented by checking all substrings ending at the current position.
function wordBreak(s, wordDict) {
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1;
i <= s.length;
i++) {
for (let j = 0;
j < i;
j++) {
if (dp[j] && wordDict.includes(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];Follow-up:
How would you optimize the solution if the dictionary is very large?
