死磕dp的第二天了
题型：dp，字符串，二维数组，背包类
来源：LeetCode
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
题目样例
代码
测试用例
测试用例
测试结果
已解答
中等
相关标签
相关企业
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为"applepenapple"可以由"apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
题目思路
纯看题解做的。
一开始笔者思路是遍历并且找到字典中的一个串，就修改原串。很显然错了（感觉这个思路+回溯的话应该对了）
然后看卡尔的讲解：她这边推荐照着背包来理解：将题目转化为 “字典能否凑齐目标串”——目标串当成背包，字典中的串自然是“宝石”，串长就是“宝石”的重量。这样就转化为一个完全背包的问题
确定要走dp后，然后就是老生常谈的dp[i]的含义：因为只要确认能否凑出来，dp[i]那就是“长度”为 i 的串在字典中能否凑出来？同时我们不能【顾头不顾腚】—— j 和 i这一块的字符串也得看一下字典中有没有
于是dp[i] = dp[j]&（substr(j,i-j)!=std::find(wd.begin(),wd.end(),str)）//当然，这一步创一个无序集合，可读性会更好些
笔者感觉不好理解的点是substr截取的长度是 【i-j】而不 +1 ，笔者感觉和 i 从1开始走有关
C++代码
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// 老实dp
int slen = s.length(),wdnum = wordDict.size();
// dp[i]的含义：长度为i的字符串，能否找到字典中的单词
//dp[i] :要看 ①dp[j] = 1（j是i前面的指针）,说明前j个位置能从字典中查到 ②[j,i]的字符串在字典中有
vector<bool> dp(slen + 1 , 0);
dp[0] = 1;
for(int i=1;i< slen+1;i++)
{
for(int j=0;j<i;j++)
{
// 长度是i-j，因为
string temp = s.substr(j,i-j);
if(dp[j] == 1 && std::find(wordDict.begin(),wordDict.end(),temp)!= wordDict.end())
dp[i] = 1;
}
}
return dp[slen];
}
};结算页面
还得继续沉淀下
