单词拆分 Ⅱ(hard)"/>
[回溯+剪枝]leetcode140:单词拆分 Ⅱ(hard)
题目:
140. 单词拆分 II
题解:
- 回溯+剪枝
- 若使用回溯法一般框架,对于
aaa...aaa
这种字符串时,会造成大量重复计算从而导致超时现象,所以我们需要加个map存放<s,result>
,这样达到剪枝的效果,优化时间。
代码如下:
class Solution {
public:vector<string> wordBreak(string s, vector<string>& wordDict) {unordered_map<string,vector<string>> m;return backtrack(m,s,wordDict);}vector<string> backtrack(unordered_map<string,vector<string>>& m,string s,vector<string>& wordDict){if(m.count(s))return m[s];//记忆化,避免重复搜索导致超时现象if(s.empty())return {""};//选择列表已空,表示生成一个可行解vector<string> result;for(const auto& word:wordDict){if(s.substr(0,word.size())!=word)continue;//剪枝,判断word是否为s的前缀//进入下一步决策,s.substr(word.size())选择列表减小vector<string> temp=backtrack(m,s.substr(word.size()),wordDict);for(const auto& it:temp){result.push_back(word+(it.empty()?"":" "+it));}}m[s]=result;return result;}
};
更多推荐
[回溯+剪枝]leetcode140:单词拆分 Ⅱ(hard)
发布评论