单词拆分

TIP

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路

var wordBreak = function(s, wordDict) {
    let dp = Array(s.length + 1).fill(false)
    dp[0] = true
    for(let j=0;j<s.length;j++){        //背包
        for(let i=0;i<wordDict.length;i++){ //物品
            if(dp[j]===true && s.substring(j,j+wordDict[i].length)===wordDict[i])
                 dp[j+wordDict[i].length] = true
            if(j+wordDict[i].length === s.length && dp[j+wordDict[i].length] === true)
                return true
        }
    }
    return false
};

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
dp[0]表示如果字符串为空的话，说明出现在字典里，所以dp[0] = true。
此处背包和物品的遍历顺序不可颠倒

单词拆分 ​

思路 ​

单词拆分

思路