做网站如何防止被坑,烟台卓通网络科技有限公司,wordpress本机,北京建设网站设计139. 单词拆分#xff08;题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台#xff09;
思路#xff1a;又是一种不同形式的背包问题#xff0c;求一个字符串是否能由字符串数组中的若干字符排列组成。首相想到排列#xff0…139. 单词拆分题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路又是一种不同形式的背包问题求一个字符串是否能由字符串数组中的若干字符排列组成。首相想到排列所以要外层遍历背包容量for循环内层遍历物品for循环。但是又不是简单的用dp数组解决排列组合的问题而是求是/否的问题。因此dp数组初始化全false遍历途中如果发现容量为j的背包可以由数组中的物品加上之前确定了的物品构成那么dp[j]就赋值true。
bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size()1, false);dp[0]true;for(int j1; js.size(); j){for(int i0; ij; i){string str s.substr(i, j-i);if(wordSet.find(str) ! wordSet.end() dp[i]){dp[j] true;}}}return dp[s.size()];
}
