Description
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
dfs(res, 0, s, "");
return res;
}
private void dfs(List<String> res, int index, String s, String cur){
if (index == 3){
if (s.length() > 1 && s.charAt(0) == '0') return;
if (Double.parseDouble(s) > 255) return;
res.add(cur+s);
return;
}
for (int i = 1; i < Math.min(s.length(), 4); i++){
String tmp = s.substring(0, i);
if (tmp.length() > 1 && tmp.charAt(0) == '0') continue;
if (Double.parseDouble(tmp) > 255) continue;
cur = cur + tmp + ".";
dfs(res, index + 1, s.substring(i), cur);
cur = cur.substring(0, cur.length()-tmp.length()-1);
}
}
}
|