单词拆分

[TieMuZhen]

法一：动态规划

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// 我们定义dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词
// 转移方程：dp[i]=dp[j] && check(s[j..i−1])

var wordBreak = function(s, wordDict) {
    const len = s.length;
    const dp = new Array(len + 1).fill(false);
    const wordSet = new Set(wordDict);
    dp[0] = true; // 长度为 0 的s能拆分成单词表单词。

    for(let i = 1; i <= len; i++){
        for(let j = 0; j < i; j++){
            // slice [)  substr []
            const word = s.substr(j, i - j);
            if(wordSet.has(word) && dp[j]){
                dp[i] = true;
                break; // i长度的子串已经可以拆成单词了，不需要j继续划分子串了
            }
        }
    }
    return dp[len];
};

法二：DFS（会超时）

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
function backtracking(s, wordSet, index){
    if(index == s.length) return true;

    for(let i = index; i <= s.length; i++){
        let word = s.slice(index, i);
        if(wordSet.has(word) && backtracking(s, wordSet, i)){
            return true
        }
    }
    return false;
}
var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    return backtracking(s, wordSet, 0);
};