义乌网站建设推广,在百度做网站多少钱,免费网站软件推荐,像优酷平台网站是怎么做的139.单词拆分
. - 力扣#xff08;LeetCode#xff09;
题目分析 初始化#xff1a;初始化一个布尔型向量dp#xff0c;大小为s.size() 1#xff0c;所有值初始化为false#xff0c;除了dp[0]被设置为true。这个布尔数组代表字符串s[0..i]能否通过拼接字典中的单词来形…139.单词拆分
. - 力扣LeetCode
题目分析 初始化初始化一个布尔型向量dp大小为s.size() 1所有值初始化为false除了dp[0]被设置为true。这个布尔数组代表字符串s[0..i]能否通过拼接字典中的单词来形成。dp[0] true的原因是一个空字符串总是可以被形成。 转换wordDict输入的wordDict被转换成一个无序集合wordset以便高效查找单词。 动态规划循环代码使用两个嵌套循环来填充dp数组 外循环从1迭代到s.size()包含。这表示当前考虑的子字符串的长度。内循环从0迭代到s.size()包含。这表示被考虑的子字符串的起始索引。对于每对(i, j)其中i j代码检查子字符串s[j, i-j]代表s从j开始长度为i-j的子字符串是否在wordset中以及dp[j]是否为true。如果这两个条件都满足意味着当前的子字符串s[j, i-j]可以通过拼接字典中的单词来形成并且j之前的子字符串也形成了有效序列所以将dp[i]设置为true。 打印dp数组在DP表填充完成后代码打印了dp数组的值显示在每个索引i处子字符串s[0..i-1]是否可以被分割成一个或多个字典中的单词。 返回值最后返回dp[s.size()]表示整个字符串s是否可以被分割成一个序列的字典单词
acm模式代码
#include iostream
#include vector
#include string
#include unordered_setclass Solution {
public:bool wordBreak(std::string s, std::vectorstd::string wordDict) {std::vectorbool dp(s.size() 1, false);dp[0] true;std::unordered_setstd::string wordset(wordDict.begin(), wordDict.end());for (int i 1; i s.size(); i ) {for (int j 0; j s.size(); j ) {if (i j) {if (wordset.find(s.substr(j , i - j)) ! wordset.end() dp[j] ) {dp[i] true;}}}}for (auto i: dp) std::cout i ;std::cout std::endl;return dp[s.size()];}
};int main() {Solution sol;std::string s leetcode;std::vectorstd::string wordDict {leet, code};bool res sol.wordBreak(s, wordDict);std::cout res: res std::endl;
}
多重背包了解
代码随想录
背包问题总结
代码随想录
