给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法1：回溯
思路：
1.首先我们要知道IP地址的每一部分为0-255，我们可以根据这个对回溯过程进行判断
2.当已经分好前三部分，对最后一部分进行判断
（1）若最后一部分长度大于3，必然不是正确的IP地址
（2）若长度==3，但字符串比255大，则不是正确IP地址
（3）若长度为0，不是正确的IP地址
（4）若长度不为1，且第一位为0，则不是正确的IP地址
3.循环遍历，且保证每部分长度不超过3，且长度为3时，进行判断是否符合IP规范
4.回溯回来时判断，这一位是否为0，若为0，则后面必然组不成IP地址，直接break 循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
private:
vector<string> res;
string temp;
public:
vector<string> restoreIpAddresses(string s) {
ip(s,0,0);
return res;
}
void ip(string s,int No,int i)
{
if(No==3)
{
string temp2=s.substr(i,s.length());
if(temp2.length()>3)
return ;
if(temp2.length()==3&&temp2>"255")
return ;
if(temp2.length()!=1&&temp2[0]=='0')
return ;
if(temp2=="")
return ;
temp+=temp2;
res.push_back(temp);
temp=temp.substr(0,temp.length()-temp2.length());
return ;
}
int k;
for(k=i;k<i+3&&k<s.length();k++)
{
string temp1=s.substr(i,k-i+1);
if(k-i+1==3)
{
if(temp1>"255")
return ;
}
temp=temp+temp1+'.';
ip(s,No+1,i+k-i+1);
temp=temp.substr(0,temp.length()-temp1.length()-1);
if(temp1=="0")
break;
}
return ;
}
};
|