Difficulty: Medium
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
1
2
| Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
|
Solution
Language: Java
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
| class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() == 0 || s.length() < 4) {
return result;
}
dfsHelper(s, 0, new ArrayList<>(), result);
return result;
}
private void dfsHelper(String s, int index, List<String> ip, List<String> result) {
if (ip.size() == 4) {
if (index == s.length()) {
result.add(String.join(".", ip));
}
return;
}
int cur = 0;
for (int i = index; i < Math.min(index + 3, s.length()); i++) {
cur = cur * 10 + (s.charAt(i) - '0');
if (cur > 255) {
break;
}
ip.add(String.valueOf(cur));
dfsHelper(s, i + 1, ip, result);
ip.remove(ip.size() - 1);
if (i == index && s.charAt(i) == '0') {
break;
}
}
}
}
|