For example:
Given
"25525511135"
,
return
["255.255.11.135", "255.255.111.35"]
. (Order does not matter)My Solution: This is a classic DFS problem. Not difficult itself, but need to pay attention to some details, such as to avoid the accumulated effects by using temporary local variables, tempLen and tempSol.
public static ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> ret = new ArrayList<String>();
String solution = "";
if(s.length()<4 || s.length()>12) return ret;
restoreIp(s, solution, ret, 1);
String str = solution;
return ret;
}
public static void restoreIp(String s, String solution, ArrayList<String> ret, int len){
String cur = "";
String restStr = "";
if(len == 4){
if(isValid(s)){
solution += s;
ret.add(solution);
}
return;
}
for(int i=0; i<3; i++){
//cur = s.substring(0,i+1);//sigh!!!!! out of index
if(s.length() <= i+1)
cur = s;
else
cur = s.substring(0,i+1);
if(isValid(cur)){
restStr = s.substring(i+1);
if(restStr.equals(""))return;
String tempSol = solution;//this is very important!!!!
int tempLen = len;//this is very important!!!!!
tempSol +=cur + ".";
tempLen++;
if(tempLen>4) return;
restoreIp(restStr, tempSol, ret, tempLen);
}
}
}
public static boolean isValid(String s){
int val = Integer.parseInt(s);
if(s.length()>1 && s.charAt(0) == '0') return false;//very important!!!!! to avoid 05
if(val>=0 && val<=255) return true;
else return false;
}
Experience: Read the comments with the code.
No comments:
Post a Comment