Restore IP Addresses
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)
Analysis
- 3-loop divides the string s into 4 substring: s1, s2, s3, s4. Check if each substring is valid.
Code
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
int len = s.length();
for (int i=1; i<4 && i<len-2;i++){
for (int j=i+1; j<i+4 && j<len-1;j++){
for (int k=j+1; k<j+4 && k<len ;k++){
String s1 = s.substring(0,i);
String s2 = s.substring(i,j);
String s3 = s.substring(j,k);
String s4 = s.substring(k,len);
if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
res.add(s1+"."+s2+"."+s3+"."+s4);
}
}
}
}
return res;
}
private boolean isValid(String s){
int len = s.length();
if (len>3 || len==0 || (s.charAt(0)=='0'&& len>1) || Integer.parseInt(s)>255){
return false;
}
else return true;
}
}
Reference
Leetcode