-
Notifications
You must be signed in to change notification settings - Fork 0
/
Restore.cpp
31 lines (31 loc) · 849 Bytes
/
Restore.cpp
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
class Restore {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
string cur = string("");
dfs(res, cur, s, 0, 0);
return res;
}
private:
void dfs(vector<string>& res, string cur, string& s, int index, int parts) {
if (index == s.size()) {
if (parts == 4) {
cur.pop_back();
res.push_back(cur);
}
return;
}
if (parts == 4) {
return;
}
int count = 0;
for (int i = index; i < min(index + 3, (int)s.size()); ++i) {
count = count * 10 + (s[i] - '0');
if (count <= 255) {
cur += s[i];
dfs(res, cur + '.', s, i + 1, parts + 1);
}
if (count == 0 && i == index) break;
}
}
};