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 {
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()) {
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);
}
}
}

}
}
``````