Problem
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.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Solution
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
var len = wordDict.length;
var dp = Array(len);
var map = {};
for (var i = 0; i < len; i++) {
map[wordDict[i]] = true;
}
return find(s, map, dp, 0);
};
var find = function (s, map, dp, index) {
if (dp[index] !== undefined) return dp[index];
var str = '';
var res = false;
var len = s.length;
if (index === len) return true;
for (var i = index; i < len; i++) {
str = s.substring(index, i + 1);
if (map[str] && find(s, map, dp, i + 1)) {
res = true;
break;
}
}
dp[index] = res;
return res;
};
Explain:
dp[i]
代表 s.substring(i)
是否可以由 wordDict
里的词组成。
Complexity:
- Time complexity : O(n^2).
- Space complexity : O(n^2).