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
| class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ret;
vector<int> tmp;
helper(s, 0, 0, ret, tmp);
return ret;
}
private:
void helper(string& s, int curNum, int index, vector<string>& ret, vector<int>& tmp)
{
if(index == s.size() || tmp.size() == 4)
{
if(index == s.size() && tmp.size() == 4)
ret.push_back(move(build(tmp)));
return;
}
int cur = s[index] - '0';
if(cur == 0 && curNum == 0)
{
tmp.push_back(0);
helper(s, 0, index + 1, ret, tmp);
tmp.pop_back();
}else
{
int num = curNum * 10 + cur;
if(num <= 255)
{
tmp.push_back(num);
helper(s, 0, index + 1, ret, tmp);
tmp.pop_back();
helper(s, num, index + 1, ret, tmp);
}
}
}
string build(vector<int>& tmp)
{
string ret;
for(auto num : tmp)
ret += to_string(num) + '.';
ret.pop_back();
return ret;
}
};
|