网站的制作方案,厦门做英文网站,wordpress超详细教程视频教程,excel服务器做网站文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;本题可以看做一个动态规划问题。其中#xff0c;字符串s是背包#xff0c;而字典中的单词就是物品。… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析本题可以看做一个动态规划问题。其中字符串s是背包而字典中的单词就是物品。题目问的是单词能否组成字符串s就是问物品能不能把背包装满。字典中的单词可以重复使用因此是一个完全背包问题。
第一步 d p [ j ] dp[j] dp[j]的含义。 d p [ j ] dp[j] dp[j]代表的是字符串长度为 j j j时该能否由字典中的单词构成。如果能则为true。第二步递推公式。如果确定 d p [ j ] dp[j] dp[j]是true且 [ j , i ] [j, i] [j,i]这个区间的子串出现在字典里那么 d p [ i ] dp[i] dp[i]一定是true。 ( j i ) (j i ) (ji)。所以递推公式是if(dp[j] [j, i]这个区间的子串出现在字典里) dp[i] true第三部元素初始化。 d p [ 0 ] dp[0] dp[0]初始化为1。第四部递归顺序。本题严格划分起来是一个排列问题。以s “applepenapple”, wordDict [“apple”, “pen”] 为例。我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。所以说本题一定是先遍历背包再遍历物品。第五步打印结果。 为了判断 [ j , i ] [j, i] [j,i]这个区间的子串出现在字典里我们构建了一个无序集合。其底层实现是一个哈希表可以在常数时间内 O ( 1 ) O(1) O(1)内进行查找。 程序如下
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, 0);dp[0] 1;for (int i 1; i s.size(); i) { // 遍历背包字符串sfor (int j 0; j i; j) { // 遍历物品(单词)string key s.substr(j, i - j);if (dp[j] wordSet.find(key) ! wordSet.end()) {dp[i] 1;}}}return dp[s.size()];}
};复杂度分析
时间复杂度 O ( n 3 ) O(n^3) O(n3)。除了两层循环以外还有需要substr返回子串它是O(n)的复杂度这里的n是substring的长度。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
# include string
# include unordered_set
using namespace std;class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, 0);dp[0] 1;for (int i 1; i s.size(); i) { // 遍历背包字符串sfor (int j 0; j i; j) { // 遍历物品(单词)string key s.substr(j, i - j);if (dp[j] wordSet.find(key) ! wordSet.end()) {dp[i] 1;}}}return dp[s.size()];}
};int main() {string s catsandog;vectorstring wordDict { cats, dog, sand, and, cat };Solution s1;bool result s1.wordBreak(s, wordDict);cout result endl;system(pause);return 0;
}end
