[回溯+剪枝]leetcode140：单词拆分 Ⅱ(hard)

单词拆分 Ⅱ(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;}
};