DFS+回溯,注意每一部分开头不能为0,如01
是非法的,另外每一部分不能大于255
:
// // Created by jt on 2020/8/31. // #include <string> #include <vector> using namespace std; class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(string s) { // write code here vector<string> res; dfs(s, res, vector<string>()); return res; } void dfs(string s, vector<string> &res, vector<string> tmp) { if (s.empty() && tmp.size() == 4) res.push_back(convert(tmp)); for (int i = 1; i <= s.size(); ++i) { if (i > 1 && s[0] == '0') break; int val = stoi(s.substr(0, i)); if (val > 255) break; tmp.push_back(s.substr(0, i)); dfs(s.substr(i), res, tmp); tmp.pop_back(); } } string convert(vector<string> vec) { string s; for (int i = 0; i < vec.size(); ++i) { s += vec[i]; if (i != vec.size() - 1) s += '.'; } return s; } };