文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的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 ) (j<i)。所以递推公式是:
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, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, 0);dp[0] = 1;for (int i = 1; i <= s.size(); i++) { // 遍历背包(字符串s)for (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, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, 0);dp[0] = 1;for (int i = 1; i <= s.size(); i++) { // 遍历背包(字符串s)for (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";vector<string> wordDict = { "cats", "dog", "sand", "and", "cat" };Solution s1;bool result = s1.wordBreak(s, wordDict);cout << result << endl;system("pause");return 0;
}
end