展示形网站怎么建,营销网址大全,南京建设局网站首页,网站被**泛解析后的解决方法类似于回溯算法中的拆分回文串题目是要求拆分字符串#xff0c;问这些字符串是否出现在字典里。但这道题可以反着来考虑#xff0c;从字典中的单词能不能组成所给定的字符串 如果这样考虑#xff0c; 这个字符串就背包#xff0c;容器字典中的单词就是一个一个物品问题就转…类似于回溯算法中的拆分回文串题目是要求拆分字符串问这些字符串是否出现在字典里。但这道题可以反着来考虑从字典中的单词能不能组成所给定的字符串 如果这样考虑 这个字符串就背包容器字典中的单词就是一个一个物品问题就转化成这些物品能不能正好装满这个背包而且这些物品可以使用多次因此这是一个完全背包类问题 动规五部曲 dp[j]数组含义把题目给定的字符串能不能用字典字符串来添满。字符串长度为j时能被字典字符串来组成就返回true否则为false递推公式道德字符串中[i, j]内容正好字典中而且dp[i]也为true的话dp[j]也就是true初始化值dp[0]必须为true否则递推出来的内容都会是false 非0下标都要初始化为false 遍历顺序给定字符串的内容是确定的也就是说字典中内容是一种排列效果来生成字符串而不是组合出多种效果来组成字符串也根本组不成 所以要先遍历背包再遍历物品
class Solution {
public:bool wordBreak(std::string s, std::vectorstd::string wordDict) {std::unordered_setstd::string wordSet(wordDict.begin(), wordDict.end());std::vectorbool dp(s.size() 1, false);dp[0] true;for (int i 1; i s.size(); i) {for (int j 0; j i; j) {std::string word s.substr(j, i - j);if (wordSet.find(word) ! wordSet.end() dp[j])dp[i] true;}}return dp.at(s.size());}
};汇总
