单词拆分（JS实现）

1 题目
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

2 思路
这道题用动态规划的方法，存储部分结构，表示字符串 s 前 i 个字符组成的字符串 s[0…i-1]是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i-1的*后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可

3代码
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
const map = {};

for (let word of wordDict) {
map[word] = true;
}

const d = [];
d[0] = true;

for (let i=0; i<s.length; i++) {
for (let j=1;j<=i+1;j++) {
let substr = s.substr(i+1-j,j);
if (d[i+1-j] && map[substr]) {
d[i+1] = true;
break;
}
}
d[i+1] = d[i+1] || false;
}

return d[s.length];
};