leetcode-139-单词拆分（递归超时，动归解决）
leetcode-139-单词拆分（递归超时，动归解决）
题目描述：
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 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要完成的函数：
bool wordBreak(string s, vector<string>& wordDict)
说明：
1、这道题给定一个string，和一个vector，vector中装着多个string类型的变量。
要求判断给定的string能不能通过在string中添加空格，从而变成一个个单词，而这些单词存在于给定的vector中。
比如给定的string是“catsandog”，给定的vector是['cats','dog','sand','and','cat']。
我们会发现并不能添加空格，进而刚好可以切分成vector中的单词。
所以返回false，如果可以切分的话，就返回true。
2、我们还是看1中的例子，我们可以发现首先有cats和cat两个选择，接下来又有sand和and两个选择。
所以这其实可以用递归来做，但是递归对于一些测试样例太耗时了。所以递归超时了。
感兴趣的同学可以看一下递归的代码，如下：（附详解）
bool dfs(string s,vector<string>& wordDict)
{
if(s.size()==0)return true;//退出条件，字符串已经为空了
int i;
for(string word:wordDict)//逐个判断可不可以是当前单词
{
i=0;
while(i<word.size())//判断可不可以到达当前单词的尾部
{
if(word[i]!=s[i])
break;
i++;
}
if(i==word.size())//如果可以到达当前单词的尾部
{
if(dfs(s.substr(i,s.size()-i),wordDict))//那么更新一下字符串，进入下一层递归
return true;
}
}
return false;//如果没有一个单词可以匹配，那么返回false
}
bool wordBreak(string s, vector<string>& wordDict)
{
return dfs(s,wordDict);//直接进入深度优先搜索的递归
}上述代码没有错误，只不过需要的时间太多了，导致超时。
递归不能做，那应该就是动态规划的做法了。
动态规划注重状态，在这道题中也就是每个字符能不能到达的状态。
比如catsandog，第一个字符c在字典中没有找到对应的word来匹配，ca也找不到对应的word来匹配，cat可以找到，cats也可以找到。
而catsa找不到直接对应的，发现前一个的cats可以到达，于是判断一下a能不能找到对应的，发现没有。
再发现再前一个的cat可以到达，于是判断一下sa能不能找到匹配的，发现不能，接着再往前找，但是都没找到。
我们由此可以发现每一位的状态定义，首先从字符串的最开始，到当前位，看一下有没有直接匹配的。
如果有，那么进行下一位的状态判断。
如果没有，那么往前看，前面哪一位状态是可以到达的，从这一位的下一位开始，到当前位结束，这一部分看可不可以在字典中直接匹配到。
如果还是不行，那么再往前找哪一位状态是可以到达的，同样从这一位的下一位开始，到当前位结束，这一部分可不可以在字典中直接匹配到。
……
最终没有找到的话，那么把这一位的状态定义为不可到达的，再进行下一位的状态判断。
代码如下：（附详解）
bool judge(string &s,int start,int end,vector<string>& wordDict)
{//判断s从start开始，到end结束，能不能在字典中找到直接匹配的
string t=s.substr(start,end-start+1);//记得要+1
for(string word:wordDict)//看一下哪个单词能够直接匹配
{
if(word==t)
return true;
}
return false;
}
bool wordBreak(string s, vector<string>& wordDict)//要完成的子函数
{
vector<bool>flag(s.size(),0);//定义一个vector，存储每一位的状态
int j;
for(int i=0;i<s.size();i++)//计算每一位的状态
{
flag[i]=judge(s,0,i,wordDict);//首先看一下能不能找到直接匹配的
if(flag[i]==0)//如果不能
{
j=i-1;//那么j=i-1，j往前面走
while(j>=0)
{
if(flag[j]==1)//如果某一位的状态是可以到达的
{
flag[i]=judge(s,j+1,i,wordDict);//那么判断一下从这一位的下一位开始，到i结束，这一部分可不可以找到匹配的
if(flag[i]==1)break;//如果可以，那么break循环，接着去计算下一位的状态
}
j--;//如果没有break循环，那么必然没有找到匹配的，那么j再往前走。如果一直没找到，那么状态不会更改，还是0
}
}
}
return (flag.back()==1);//最终看一下最后一位的状态是不是可以到达的，如果是，那么返回true
}上述代码实测4ms，beats % of cpp submissions。
笔者自己的个人总结，动态规划有两个特点：
1、强调每一位的状态。
2、每一位的状态计算往往跟前几位有关系，也就是存在对前面状态的依赖性。
有时候是对前面一位状态的依赖，有时候是对前面几位，主要看解决题目的需要而定，而这道题是对前面的所有状态的依赖。
还是挺有趣的一道题目。
腾讯云开发者
