题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
解题方法
一维动态规划（动态规划我的痛orz）
ps:不了解一维动态规划的可以移步左程云老师的视频
思路
题目分析
对于题目给出的例子：
s = “leetcode”, wordDict = [“leet”, “code”]
对字符串leetcode从后向前遍历（其实从前往后也是一样的）
对于动态规划问题：我们可以递归的思考
1. 当子串长度为1时，如果“e”存在于字典中，那么需要判断剩下的字符串“leetcod”是否在字典中
2. 当子串长度为2时，如果“de”存在于字典中，那么需要判断剩下的字符串“leetco”是否在字典中
3. 当子串长度为3时，如果“ode”存在于字典中，那么需要判断剩下的字符串“leetc”是否在字典中
4. ……以此类推
其中一种情况为true，结果就为true，因为有一种拆分形式就行。
我们定义函数f(i)表示：从s[0]开始长度为i的字是否都是由字典中的单词组成(牢记这个定义，下面看不明白的时候回来想想)。
之所以用长度而不用下标是为了防止子串长度为0时出现下角标为负数的情况，改写为动态规划会出现复杂的边界判断
f(i)就表示s[0,i-1]是否由字典中的单词拼接而成，所以问题就转化为了判断s[0,i-1]是不是由字典中的单词组成的
细节
我们假设字串s[0,i-1]从s[j]处拆分，s就可以拆分为两个字符串：s[0,j-1]和s[j,i-1]。只要这两部分都由字典中的单词组成，s[0,i-1]就可以成功拆分！>w<
还记得我们刚才给f(i)的定义吗？
从s[0]开始长度为i的字是否都是由字典中的单词组成。
所以s[0, j-1]是否能拆分可以由f(j)表示，而剩下的字串，也就是s[j,i-1]我们直接与字典中的单词匹配。
为了方便查找，我们直接将字典数组放入哈希表（也可以自己实现字典树哦~），找到字典中最长的单词，取它的长度max_len。我们控制s[j, i-1]的长度在[0, max_len]就可以直接在哈希表中查找！>w<如果查找到s[j,i-1]在哈希表中存在，就说明s[j, i-1]是字典中的单词( •̀ ω •́ )y！
代码实现
我们再加上记忆化搜索，一个简单的递归版本就实现了(竟然意外的的通过了( •̀ ω •́ )y)：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int n = s.size();
vector<int>dp(n+1, -1);//-1表示还没有存储过值
int max_len = INT_MIN;
unordered_set<string> hash;
for(auto word : wordDict)
{
max_len = max(max_len, (int)word.size());
hash.insert(word);
}
return f(s, hash, n, max_len, dp);
}
bool f(string s, unordered_set<string>& hash, int i, int max_len, vector<int> &dp)
{
if(i == 0)
{
return true;//空串符合要求
}
if(dp[i] != -1)
{
return dp[i];//记忆化搜索
}
int res = false;
//j是s2的开头 i - max_len是s2开头的最小下标 因为 s2的长度为 i - j <= max_len j最小不能小于0
for(int j = i - 1; j >=max(i - max_len, 0); j--)
{
if(hash.count(s.substr(j, i - j)) && f(s, hash, j, max_len, dp))
{
res = true;
}
}
dp[i] = res;
return res;
}
};
因为不确定j在什么位置可以拆分成功，所以只能将从j到i-1的长度小于max_len的所有可能都尝试一遍
有人可能会想：既然s[j, i-1]可以直通过哈希表判断，为什么s[0,j-1]不行呢？注意一下，s[j,i-1]之所以能够通过哈希表判断，是因为我们始终控制s[i, i-1]的长度小于最大单词长度，而我们无法控制和判断s[0, j-1]的长度.
由此，我们就可以通过这个递归+记忆化搜索改写出动态规划的版本：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int n = s.size();
vector<int>dp(n+1, 0);//默认为false
int max_len = INT_MIN;
unordered_set<string> hash;
for(auto word : wordDict)
{
max_len = max(max_len, (int)word.size());
hash.insert(word);
}
dp[0] = true;
for(int i = 1; i <= n; i++)
{
for(int j = i - 1; j >=max(i - max_len, 0); j--)
{
if(hash.count(s.substr(j, i - j)) && dp[j])
{
dp[i] = true;
}
}
}
return dp[n];
}
}；
dp[i]的定义与f(i)相同，我们将用到记忆化搜索和f(i)的部分都换成dp数组，每个dp[i-1]位置的判断都依赖于前面的dp，这样我们就将从顶到底（从复杂到简单）的递归，改写为了从底到顶（从简单到复杂）的动态规划！>w<
