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
解题思路：首先想到利用dfs去做，具体的：从0开始遍历字符串s，找到第一个出现在给定字典中的字符串，然后进入递归过程，
将s中剩下的字符串作为递归的输入，递归停止的条件为：遍历完s中最后一个字符时恰好截取的子串是给定字典中的单词。
结果：29/36个测试用例时出现超时的错误提示
原因分析：当输入字符串中存在大量的重复字符时，如下图中的'a',算法每遍历一个字符就进入递归过程，多次调用堆栈，造
成大量的空间和时间的开销，同时容易造成栈溢出。
解决方法：应该注意到字典中存在'a', 'aa', 'aaa'，但s中存在大量重复字符时dfs却一个一个字符处理，实际可以从0开始将
s的所有子串作为处理对象，这就用到了动态规划的思想，即创建一个bool数组dp[]，初始化为false, 存储每个子串是否是给定
字典中的单词，dp[i]即存储前i个节点所组成字符串是否为给定字典中的单词，后面对每个节点的判断都要利用前面dp[i]的信息。
具体代码：
class Solution {
public:
bool wordBreakRecursion(string s, int start, map<string, char> &wordMap)
{
if (start == s.size())
{
return true;
}
for (int i = start; i < s.size(); i++)
{
string substr = s.substr(start, i + 1 - start);
if (wordMap[substr] == 'y')
{
if (!wordBreakRecursion(s, i+1, wordMap)) //递归调用
{
continue;
}
else
{
return true;
}
}
}
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
int nWord = wordDict.size();
map<string, char> wordMap;
for (int i = 0; i < nWord; i++)
{
wordMap[wordDict[i]] = 'y'; //map便于查找
}
return(wordBreakRecursion(s, 0, wordMap));
}
};
DP算法：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
const int n = s.size();
bool flag[n+1]; //新建一个数组记录s的子序列是否可以拆分
memset(flag, 0, (n+1)*sizeof(bool));
//map<string, char> wordMap;
flag[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
//查找该字符串是否是给定字典中的单词，j是字符串的起点，i是终点
if (flag[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i-j)) != wordDict.end())
{
flag[i] = true;
break;
}
}
}
return flag[n];
}
};
下面给出测试结果：