LeetCode140. 单词拆分II
题目:
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例:
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
题目分析:
动态规划+回溯法DFS
代码:
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> result;
string stc;
vector<bool> able(s.size() + 1, false);
vector<vector<string>> set(s.size() + 1, vector<string>());
able[0] = true;
for (size_t i = 1; i <= s.size(); ++i)
{
vector<string> temp;
for (size_t j = 0; j<i; ++j)
{
if (able[j]==true&&contain(s, wordDict, temp, j, i - 1))
{
able[i] = true;
}
}
set[i] = temp;
}
int j = 0, k = set[s.size()].size();
if (!able[s.size()])
return result;
word(s, stc, result, wordDict, able, set, s.size(), j);
if (!result.empty())
{
for (size_t i = 0; i<result.size(); i++)
result[i] = result[i].substr(0, result[i].size() - 1);
}
return result;
}
bool word(string s, string& stc, vector<string>& result, vector<string>& wordDict, vector<bool>& able, vector<vector<string>>& set, int start, int j) {
if (start == 0)
{
result.push_back(stc);
return true;
}
if (start<0)
return false;
if (able[start])
{
int k = set[start].size();
while (j<k)
{
stc = stc.insert(0," ").insert(0, set[start][j]);
word(s, stc, result, wordDict, able, set, start - set[start][j].size(), 0);
stc = stc.substr(set[start][j].size()+1);
if (start == s.size()&&j>=k)
return false;
++j;
}
return false;
}
return false;
}
bool contain(string s, vector<string>& wordDict, vector<string>& temp, int start, int end) {
string t=s.substr(start,end-start+1);
for(auto& word:wordDict)
if(word==t)
temp.push_back(word);
if(temp.empty())
return false;
else
return true;
}
};