Tuesday, February 18, 2014

Leetcode: 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)

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