给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.‘ 分隔。
例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
//样例一
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
//样例二
输入:s = "0000"
输出:["0.0.0.0"]
//样例三
输入:s = "1111"
输出:["1.1.1.1"]
//样例四
输入:s = "010010"
输出:["0.10.0.10","0.100.1.0"]
//样例五
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
采用dfs回溯算法,每次dfs只分析IP地址中的其中一段,这样就会有函数dfs(string s, int id, int start)。其中id是当前分析的段数,start是此段从哪开始分析。
但是会有三个条件判断:
接下来就是函数分析主体:
会从start开始每次取一个数字分析下一段(for循环),也就是分析当前IP地址的第Id段为1、2、3位数字的情况。如果分析不成功,根据递归调用会回溯到上一个分析的状态。
#include <iostream>
#include<string>
#include<vector>
using namespace std;
vector<string> res;
int num[4];
void dfs(string s, int id, int start) {
if (id == 4) {
if (start == s.length()){
string str;
str = str + to_string(num[0]) + ‘.‘ + to_string(num[1]) + ‘.‘ + to_string(num[2]) + ‘.‘ + to_string(num[3]);
res.push_back(str);
}
return;
}//已经分析出来了
if (start == s.length())
return;
//分析到尾但是没有四段
if (s[start] == ‘0‘) {
num[id] = 0;
dfs(s, id + 1, start + 1);
}
//当前分析的第一个数字是0
int addr = 0;//存放当前第id段的地址
for (int i = start; i < s.length(); i++) {
addr = addr * 10 + s[i] - ‘0‘;
if (addr > 0 && addr < 256) {
num[id] = addr;
dfs(s, id + 1, i + 1);
}
else break;
}
}
int main()
{
string s;
cin >> s;
dfs(s, 0, 0);
for (int i = 0; i < res.size(); i++) {
cout << res[i]<<endl;
}
return 0;
}
原文:https://www.cnblogs.com/MrDaddy/p/14845117.html