Keshawn_lu's Blog

Leetcode 93. 复原IP地址

字数统计: 519阅读时长: 2 min
2020/08/09 Share

题目简介:

给定一个只包含数字的字符串,复原它并返回所有可能的 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;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: