代码随想录打卡—day28—【回溯】— 回溯基础练习 4.17

本文主要是介绍代码随想录打卡—day28—【回溯】— 回溯基础练习 4.17，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 93. 复原 IP 地址

也是类似前一天的分割回文串。可以用我的字符之间0101的思路，也可以直接用[start_idx,i]选取子串的方法，选取后者，代码简洁一点：

class Solution {
public:vector<string> ans;string path;void dfs(int u,int start_idx,string s){if(u == 4 && start_idx == s.size()){string tmp_ans = path;tmp_ans.pop_back();ans.push_back(tmp_ans);return;}for(int i = start_idx; i < s.size() && i - start_idx <= 2;i++){string tmp = s.substr(start_idx, i - start_idx + 1);int tmp_int = 0;for(int j = 0; j < tmp.size();j++){tmp_int += (tmp[j] - '0');if(j != tmp.size()-1)tmp_int*=10;}if(tmp.size() > 1 && tmp[0] == '0' || tmp_int > 255)continue;else{path += (tmp+'.');dfs(u+1,i+1,s);path.erase(path.size() - (tmp.size()+1));}}}vector<string> restoreIpAddresses(string s) {dfs(0,0,s);return ans;}
};

这篇关于代码随想录打卡—day28—【回溯】— 回溯基础练习 4.17的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---