LeetCode - Restore IP Addresses
Problem description
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.
Example:
1
2
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Analysis
This is a standard backtrack problem.
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
37
38
39
40
41
42
43
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), s, 0);
return res;
}
void backtrack(List<String> res, List<String> list, String s, int index){
if (list.size() == 4 || index == s.length()){
if (list.size() == 4 && index == s.length()){
StringBuilder sb = new StringBuilder();
for (String str:list){
// check if it forms like "010"
if (str.charAt(0) == '0' && str.length() != 1){
return;
}
int v = Integer.valueOf(str);
if (v < 0 || v > 255){
return;
}
sb.append(str);
sb.append(".");
}
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
}
return;
}
for (int i = index + 1; i <= Math.min(s.length(), index + 3); i++){
String substring = s.substring(index, i);
list.add(substring);
backtrack(res, list, s, i);
list.remove(list.size() - 1);
}
}
}
What to improve
- when dealing with numbers, be careful about numbers start with 0.