题目简介：
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.'分隔。
示例:
1
2
| 输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
|
思路：
递归，函数形式为dfs(int pointnum, int lastpoint, string& s, string& temp)。
其中pointnum代表已经加点的数量，lastpoint代表上次加点的位置(在s中的位置)，s代表初始字符串，temp代表加了点后的ip地址，用于存放答案字符串。
若pointnum == 3，则我们从上次加点的位置的后一个位置到字符串的末尾，即s[lastpoint + 1 ... s.size() - 1]，若这串字符代表的数字0 <= num <= 255，则说明此为正确的IP地址，压入结果数组。
若pointnum != 3，则我们从上次加点的位置往后遍历，寻找到可加下一个点的位置，并继续递归即可。
tips:
- 由于IP地址除去点以外最多12个字符，所以
s.size() > 12时直接返回{}，防止超时。
- 在
validNum()函数中，需要注意特殊情况的处理。
- 往
temp中插入点时，需要加上已有点的数量。
代码如下：
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public:
vector<string> res;
bool validNum(string& s, int left, int right){
if(s[left] == '0' && right != left)
return false;
if(left > right)
return false;
int sum = 0;
for(int i = left; i <= right; i++){
sum = sum * 10 + (s[i] - '0');
if(sum > 255)
return false;
}
return true;
}
void dfs(int pointnum, int lastpoint, string& s, string& temp){
if(pointnum == 3){
if(validNum(s, lastpoint + 1, s.size() - 1)){
res.push_back(temp);
return;
}
}
for(int i = lastpoint + 1; i < s.size(); i++){
if(validNum(s, lastpoint + 1, i)){
temp.insert(temp.begin() + pointnum + i + 1, '.');
dfs(pointnum + 1, i, s, temp);
temp.erase(pointnum + i + 1, 1);
}
else
return;
}
}
vector<string> restoreIpAddresses(string s) {
string temp = s;
if(s.size() > 12)
return {};
dfs(0, -1, s, temp);
return res;
}
};
|
