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
| class Solution {
List<String> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
char[] cs;
int n;
public List<String> restoreIpAddresses(String s) {
cs = s.toCharArray();
n = cs.length;
dfs(0);
return ans;
}
private void dfs(int idx) {
if (path.size() > 4) return;
if (idx == n) {
if (path.size() == 4) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 4; ++i) {
builder.append(path.get(i)).append(".");
}
ans.add(builder.substring(0, builder.length() - 1));
}
} else {
for (int i = idx; i < n; ++i) {
int x = 0;
for (int j = idx; j <= i; ++j) x = x * 10 + (cs[j] - '0');
if (cs[idx] == '0' && i != idx) break;
if (x > 255) break;
path.add(x);
dfs(i + 1);
path.remove(path.size() - 1);
}
}
}
}
|
wechat
