Skip to content

单词拆分

问题

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

答案

js
var wordBreak = function(s, wordDict) {
    let dp=new 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(j>=wordDict[i].length){
                if(s.slice(j-wordDict[i].length,j)===wordDict[i]&&dp[j-wordDict[i].length]){
                    dp[j]=true;
                }
            }
        }
    }
    return dp[s.length];
};

扩展