时间限制:1秒 空间限制:32768K
题目描述
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].
A solution is["cats and dog", "cat sand dog"].
我的代码
图1 递归解法class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> res;
if(dict.find(s)!=dict.end())
res.push_back(s);
int siz=s.size();
for(int i=1;i<siz;i++){
string word=s.substr(i);//截取至末尾
if(dict.find(word)==dict.end())
continue;
vector<string> tmpRes=wordBreak(s.substr(0,i),dict);
combine(tmpRes,word);
res.insert(res.begin(),tmpRes.begin(),tmpRes.end());
}
return res;
}
void combine(vector<string> &inp, const string &word){
int siz=inp.size();
for(int i=0;i<siz;i++)
inp[i]+=(" "+word);
}
};
运行时间:7ms
占用内存:608k
网友评论