140. 单词拆分 II(dfs)

链接140. 单词拆分 II题解140. 单词拆分 II - 力扣LeetCodeclass Solution { private: // 表示以key为下标开始value表示可以到达字符串末尾的清空 unordered_mapint, vectorstring ans; unordered_setstring wordSet; public: vectorstring wordBreak(string s, vectorstring wordDict) { wordSet unordered_set(wordDict.begin(), wordDict.end()); backtrack(s, 0); return ans[0]; } void backtrack(const string s, int index) { if (!ans.count(index)) { // 如果打到达末尾直接返回并且给ans[index]一个空 if (index s.size()) { ans[index] {}; return; } ans[index] {}; for (int i index 1; i s.size(); i) { //substr表示以index为开头长度为i-index string word s.substr(index, i - index); // 如果字典有这个 if (wordSet.count(word)) { // 回溯下一个字符以i为开始 backtrack(s, i); // 通过以i为开头的字符串获得以index为开头字符串的情况 // 如果succ为空表示当前word为最后一个字符串 for (const string succ: ans[i]) { ans[index].push_back(succ.empty() ? word : word succ); } } } } } };class Solution { public: vectorstring wordBreak(string s, vectorstring wordDict) { if (s.size() 0 || wordDict.size() 0) { return {}; } unordered_setstring dict(wordDict.begin(), wordDict.end()); vectorstring result; unordered_mapint, vectorstring memo; int begin 0; // 以begin开头返回的组合 return dfs(begin, s, result, dict, memo); // return memo[0]; } vectorstring dfs(int begin, const std::string s, vectorstring result, unordered_setstring dict, unordered_mapint, vectorstring memo) { // 如果begin计算过 if (memo.find(begin) ! memo.end()) { return memo[begin]; } if (begin s.size()) { string tmp; memo[begin].push_back(tmp); return {tmp}; } vectorstring sub_result; for (int i begin; i s.size(); i) { std::string str s.substr(begin, i-begin1); if (dict.find(str) dict.end()) { continue; } vectorstring suffix dfs(i1, s, result, dict, memo); // 组装一下i1后面返回成功的组合 for (auto s : suffix) { // 如果s是空则直接放入 if (s.empty()) { sub_result.push_back(str); } else { // 组合一下 string sub_str str s; sub_result.push_back(move(sub_str)); } } } // 存储计算结果 memo[begin] sub_result; return sub_result; } };class Solution { public: vectorstring wordBreak(string s, vectorstring wordDict) { if (s.size() 0 || wordDict.size() 0) { return {}; } unordered_setstring dict(wordDict.begin(), wordDict.end()); vectorstring result; unordered_mapint, vectorstring memo; int begin 0; // 以begin开头返回的组合 return dfs(begin, s, result, dict, memo); // return memo[0]; } vectorstring dfs(int begin, const std::string s, vectorstring result, unordered_setstring dict, unordered_mapint, vectorstring memo) { // 如果begin计算过 if (memo.find(begin) ! memo.end()) { return memo[begin]; } if (begin s.size()) { string tmp; memo[begin].push_back(tmp); return {tmp}; } vectorstring sub_result; for (int i begin; i s.size(); i) { std::string str s.substr(begin, i-begin1); if (dict.find(str) dict.end()) { continue; } vectorstring suffix dfs(i1, s, result, dict, memo); // 组装一下i1后面返回成功的组合 for (auto s : suffix) { // 如果s是空则直接放入 if (s.empty()) { sub_result.push_back(str); } else { // 组合一下 string sub_str str s; sub_result.push_back(move(sub_str)); } } } // 存储计算结果 memo[begin] sub_result; return sub_result; } };