无锡网站优化哪家好,wordpress简便安装,89点班组建设网站,微信如何制作自己的公众号139.单词拆分
题目链接#xff1a;139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 文章讲解/视频讲解#xff1a;https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88…139.单词拆分
题目链接139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 文章讲解/视频讲解https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html 思路
这是一个完全背包问题其中wordDict中的每个字符串为物品字符串s为背包。dp[j]代表了在当前遍历下由s的下标范围[0, j - 1]构成的子字符串能不能被拼接出来。由于这里需要考虑到每个字符串的拼接先后顺序因此需要采用先遍历背包容量再遍历物品的方法。初始赋值时令dp[0] true其余初值均赋予false。
dp数组的递推式为
dp[j] dp[j] || (dp[j - wordDict[i].size()] s.substr(j - wordDict[i].size(), wordDict[i].size()) wordDict[i]);C实现
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {vectorbool dp(s.size() 1, false);dp[0] true;for(int j 0;js.size();j){for(int i 0;iwordDict.size();i){if(j wordDict[i].size()){dp[j] dp[j] || (dp[j - wordDict[i].size()] s.substr(j - wordDict[i].size(), wordDict[i].size()) wordDict[i]);}}}return dp[s.size()];}
};多重背包 文章讲解https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html
