restore ip address
题目
题意：把一个数字串用小数点分隔成4段，问共能形成多少个合法的IP地址。
分析：
这是一个简单的搜索问题。需要注意的是如下边界条件
- 每一段的数字必须在0-255之间
- 数字不能有前导0
代码:
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
| class Solution {
public:
vector<string> restoreIpAddresses(string s) {
// 看起来像是简单的搜索问题。一个IP地址的一段只能是0-255，因此长度最多为3
// 中间可以进行剪枝
// 不知道有没有什么奇怪的边界情况
// 果然是有的，比如不应该有前导0
// 以及是否需要去重？
// 事实说明不需要。
vector<string> ans;
int len[4], byte[4];
// 因为模板的原因，必须cast成int？
for (len[0] = 1; len[0] <= min(3, (int) s.length()); len[0]++) {
byte[0] = stoi(s.substr(0, len[0]));
if (byte[0] > 255)
continue;
// 考虑前导0问题
if (len[0] > 1 && s[0] == '0')
continue;
for (len[1] = 1; len[1] <= min(3, (int) s.length() - len[0]); len[1]++) {
byte[1] = stoi(s.substr(len[0], len[1]));
if (byte[1] > 255)
continue;
if (len[1] > 1 && s[len[0]] == '0')
continue;
for (len[2] = 1; len[2] <= min(3, (int) s.length() - len[0] - len[1]); len[2]++) {
byte[2] = stoi(s.substr(len[0] + len[1], len[2]));
if (byte[2] > 255)
continue;
if (len[2] > 1 && s[len[0]+len[1]] == '0')
continue;
len[3] = s.length() - len[0] - len[1] - len[2];
// 除了要考虑位数不够的情况，也要考虑位数太多的情况，这也是不合法的
if (len[3] <= 0 || len[3] > 3)
continue;
byte[3] = stoi(s.substr(len[0] + len[1] + len[2], len[3]));
if (byte[3] > 255)
continue;
if (len[3] > 1 && s[len[0]+len[1]+len[2]] == '0')
continue;
string ip = s.substr(0, len[0]) + "." + s.substr(len[0], len[1]) + "." +
s.substr(len[0] + len[1], len[2]) + "." + s.substr(len[0] + len[1] + len[2], len[3]);
ans.push_back(ip);
// cout << ip << endl;
}
}
}
return ans;
}
};
|
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com
文章标题:restore ip address
本文作者:红尘追风
发布时间:2015-05-01, 18:13:46
原始链接:http://www.micernel.com/2015/05/01/restore_ip_address/
版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。