leetcode 139

// 动态规划
// state[i]表示s[0]到s[i]都能被切割成功
var wordBreak = function (s, wordDict) {
    if (s.length === 0) {
        return false
    }
    const dir = new Map();
    for (let v of wordDict) {
        dir.set(v, 1);
    }
    const state = new Array(s.length + 1).fill(false);
    state[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = i - 1; j >= 0; j--) {
         // state[i]为true是state[j]为true且s[j]到s[i]都为true
            if (state[j] && dir.get(s.slice(j, i))) {
                state[i] = true;
                break;
            }
        }
    }
    return state[s.length]
};