回溯算法

文章目录

5520. 拆分字符串使唯一子字符串的数目最大93. 复原IP地址131.分割回文串

5520. 拆分字符串使唯一子字符串的数目最大

主要思路：

这一题是经典的dfs,你就不断的拆字符串，每一次拆到一个子串时加入unordered_set前，要检查是否重复，如果重复那就不加入，这个set起到了visited的作用用一个变量去搜索可能的答案，节省空间，当然要用到回溯了 代码如下： class Solution { public: int ans; void solve(string &s, unordered_set<string> &st, int i, int deep) { if (i == s.size()) { ans = max(ans, deep); return; } int n = s.size(); // i是起点:从[0,size()),尾哨兵取不到，return了 // j是截取的终点：从[1,size()] for (int j = i + 1; j <= n; ++j) { string sub = s.substr(i, j - i); if (st.find(sub) != st.end()) continue; st.insert(sub); // 这个传参j传的好 solve(s, st, j, deep + 1); st.erase(sub); } } int maxUniqueSplit(string s) { unordered_set<string> st; ans = 0; solve(s, st, 0, 0); return ans; } };

93. 复原IP地址

主要思路：* 切割问题 切割问题

想到暴力搜索，字符串切割的方法是从周赛的题解上学习的 起点start:[0,size()), 终点end:[1,size()] for(int end=start+1; end<=size();end++){ str = s.substr(star,end-start); } track是字符串回溯，有些特别，我用了substr()的技巧 // 93.复原IP地址 vector<string> restoreIpAddresses(string s) { string track = ""; vector<string> res; // 如果长度不够，不搜索 if (s.length() < 4 || s.length() > 12) { return res; } int pointNum = 0; dfs11(track, res, s, 0, pointNum); return res; } void dfs11(string &track, vector<string> &res, string s, int start, int pointNum) { if (pointNum == 3) { // 逗点数量为3时，分隔结束 // 判断第四段子字符串是否合法(最后一段)，如果合法就放进result中 if (isValid2(s.substr(start, s.size() - start))) { string t = track + s.substr(start, s.size() - start); res.push_back(t); } return; } // 从起始位置开始构造字段字符串串 // start:[0,size() ) 起点 // 截取终点 end: [1, size()] for (int end = start + 1; end <= s.length(); end++) { string tmp = s.substr(start, end - start); // 判断 [startIndex,i] 这个区间的子串是否合法 if (!isValid2(tmp)) { return; } // 合法，在i的后面插入一个逗点 tmp += "."; int length = track.size(); track += tmp; dfs11(track, res, s, end, pointNum + 1); // 回溯时删除 track = track.substr(0, length); // 把tmp与.删除 } } bool isValid2(string tmp) { int sum = 0; for (int i = 0; i < tmp.length(); i++) { if ('0' <= tmp[i] && tmp[i] <= '9') { sum = (tmp[i] - '0') + sum * 10; } else { return false; } } if (sum == 0 && tmp.size() != 1) { return false; } if (sum != 0 && tmp[0] == '0') { return false; } if (sum > 255 || sum < 0) { return false; } return true; }

131.分割回文串

主要题意： 就是不断切割字符子串，判断是否是回文串，判断回文串用一个while循环就可以了；

// 131.分割回文串 vector<vector<string>> partition(string s) { // 用DFS, 回溯需要用在track，因为track是全局变量，每一个递归子树产生的结果在track push进res后，需要撤销选择 vector<vector<string>> res; vector<string> track; if (0 == s.length()) return res; backtrack(res, track, s, 0); return res; } void backtrack(vector<vector<string>> &res, vector<string> &track, string s, int start) { if (start == s.length()) { res.push_back(track); return; } for (int end = start + 1; end <= s.length(); end++) { if (isPalind(s.substr(start, end - start))) { track.push_back(s.substr(start, end - start)); // 递归树第一层for循环 取 a ab aab backtrack(res, track, s, end); // 进入第一层for循环a的递归子树：a->ab track.pop_back(); // 针对第一层for循环a pop掉 准备进入第一层for循环 ab的递归子树 } } } bool isPalind(string s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; }