C++刷leetcode（93. 复原IP地址）【回溯】
题目描述：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
void dfs(string& s, int cur, vector<string>&temp, vector<string>& res){
if(cur > s.size() || temp.size() > 4 || (cur >= s.size() && temp.size() < 4)) return;
if(temp.size() == 4){
if(cur == s.size()){
string store;
for(auto cha : temp) store = store + cha + ".";
res.push_back(store.substr(0, store.size() - 1));
}
return;
}
vector<string> store1 = {s.substr(cur, 1), s.substr(cur, 2), s.substr(cur, 3)};
for(int i = 0; i < 3; i++){
if(store1 == '0' && store1.size() > 1) continue;
if(stoi(store1) <= 255){
temp.push_back(store1);
dfs(s, cur + i + 1, temp, res);
temp.pop_back();
}
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> res;
vector<string> temp;
dfs(s, 0, temp, res);
return res;
}
};
页:
[1]