93 Restore IP Addresses – Medium¶
Problem:¶
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example: Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Thoughts:¶
Modified DFS. Keep a variable to keep current potential solution – String.
Keep how many parts to go.
For each visit, there are three possibilities to go deep level. x, xx, xxx.
Only go deep when the possibility is valid.
Solutions:¶
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
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new LinkedList<String>();
dfs(s, result, "", 0, 12, 4);
return result;
}
private void dfs(String s, List<String> result, String curr, int start, int max, int min) {
if (s.length() - start > max || s.length() - start < min) {
return;
}
if (max == 0 && start == s.length()) {
result.add(curr.substring(1));
return;
}
if (s.charAt(start) == '0') {
dfs(s, result, curr + ".0", start + 1, max - 3, min - 1);
return;
}
for (int i = 0; i < 3; i ++) {
if (start + i + 1 <= s.length()) {
int tmp = Integer.parseInt(s.substring(start, start + i + 1));
if (tmp >=0 && tmp <= 255) {
dfs(s, result, curr + "." + tmp, start + i + 1, max - 3, min - 1);
}
}
}
}
}