8000 added 123. Restore IP Addresses · codingMan1216/LeetCode@d1fedd0 · GitHub
[go: up one dir, main page]
Skip to content

Commit d1fedd0

Browse files
pezypezy
committed
added 123. Restore IP Addresses
1 parent 74aa11a commit d1fedd0

File tree

3 files changed

+117
-0
lines changed

3 files changed

+117
-0
lines changed

‎123. Restore IP Addresses/README.md

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
这道题的题意很好理解。
2+
3+
给你一堆数字：
4+
5+
25525511135
6+
7+
让你分割成符合要求的形式：
8+
9+
255.255.11.135
10+
255.255.111.35
11+
12+
13+
那么很自然的，首先考虑的是，什么叫符合要求。
14+
15+
IPV4的地址有以下几个特点：
16+
17+
1. 必须 4 段
18+
2. 每一段是 0 ~ 255 之间
19+
20+
作为字符串，可能会出现 010 的情况，必须避免。故再加一条
21+
22+
3) 长度大于 1 的子段，不能以 0 开头。
23+
24+
可以看到，三条规定里，后两条都是针对分割后的每一段而言的。我们写一个函数来验证合法性：
25+
26+
```cpp
27+
bool valid(const string &s) {
28+
if (s.size() > 1 && s[0] == '0') return false;
29+
int num = std::stoi(s);
30+
return 0 <= num && num <= 255;
31+
}
32+
```
33+
34+
假定以下情况：
35+
36+
255. | 25511135
37+
^ ^
38+
ip origin string.
39+
40+
在 0 ~ 255 中间，也意味着子段的长度只可能是 1、2、3，我们在试探的时候仅需试探三次，写成循环：
41+
42+
255
43+
^
44+
section: 2, 25, 255
45+
46+
对于第一条，我们设定只能有 4 part, 每一次尝试都减 1.
47+
48+
```cpp
49+
for (size_t i=1; i<4; ++i) {
50+
if (origin.size() < i) break; // 如果分了三段，最后一段不够长，stop
51+
string section = origin.substr(0, i); // 可能的子串
52+
if (valid(section)) {
53+
if (part != 1) section.append("."); // 除了最后一段，每一段后面用 `.` 分隔
54+
dfs(origin.substr(i), ip+section, part-1);
55+
}
56+
57+
}
58+
```
59+
60+
这明显是一个 DFS，那么递归必然有其退出条件。这里便是 `part == 0` 的情况。
61+
62+
```cpp
63+
if (part == 0) {
64+
if (origin.empty()) ret.push_back(ip); // 最后一段，恰好分割完，入兜
65+
return; // 其他情况都不是我们想要的
66+
}
67+
```
68+
69+
总体来说，是比较简单的 DFS 方案。AC

‎123. Restore IP Addresses/main.cpp

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
using namespace std;
4+
5+
int main()
6+
{
7+
Solution s;
8+
vector<string> ips = s.restoreIpAddresses("25525511135");
9+
for (const auto &ip : ips)
10+
cout << ip << endl;
11+
}

‎123. Restore IP Addresses/solution.h

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
#include <vector>
2+
using std::vector;
3+
#include <string>
4+
using std::string;
5+
6+
class Solution {
7+
vector<string> ret;
8+
9+
bool valid(const string &s) {
10+
if (s.size() > 1 && s[0] == '0') return false;
11+
int num = std::stoi(s);
12+
return 0 <= num && num <= 255;
13+
}
14+
15+
void restore(const string &origin, const string &ip, int part)
16+
{
17+
if (part == 0) {
18+
if (origin.empty()) ret.push_back(ip);
19+
return;
20+
}
21+
22+
for (size_t i=1; i<4; ++i) {
23+
if (origin.size() < i) break;
24+
string section = origin.substr(0, i);
25+
if (valid(section)) {
26+
if (part != 1) section.append(".");
27+
restore(origin.substr(i), ip+section, part-1);
28+
}
29+
}
30+
}
31+
32+
public:
33+
vector<string> restoreIpAddresses(string s) {
34+
if (s.size() >= 4 && s.size() <= 12) restore(s, "", 4);
35+
return ret;
36+
}
37+
};

0 commit comments

Comments
 (0)
0