-
Notifications
You must be signed in to change notification settings - Fork 73
Expand file tree
/
Copy pathRestoreIPAddress.java
More file actions
63 lines (54 loc) · 1.77 KB
/
RestoreIPAddress.java
File metadata and controls
63 lines (54 loc) · 1.77 KB
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package algorithm.lc;
import java.util.ArrayList;
/**
* 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)
*
*/
// O(3^4) space, O(3^4) time, actually both are constant
public class RestoreIPAddress {
public class Solution {
// use three levels of loop
public ArrayList<String> restoreIpAddresses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<String> res = new ArrayList<String>();
for (int first = 1; first < s.length(); ++first) {
if (!isValid(s, 0, first))
break;
for (int second = first + 1; second < s.length(); ++second) {
if (!isValid(s, first, second))
break;
for (int third = second + 1; third < s.length(); ++third) {
if (!isValid(s, second, third))
break;
if (isValid(s, third, s.length())) {
// IP is valid
StringBuilder sb = new StringBuilder();
sb.append(s.substring(0, first)).append('.');
sb.append(s.substring(first, second)).append('.');
sb.append(s.substring(second, third)).append('.');
sb.append(s.substring(third));
res.add(sb.toString());
}
}
}
}
return res;
}
private boolean isValid(String s, int start, int end) {
if (end - start > 3 || (end - start > 1 && s.charAt(start) == '0')) {
return false;
}
int num = Integer.parseInt(s.substring(start, end));
if (num < 256 && num >= 0) {
return true;
}
return false;
}
}
}