Very easy understanding backtracking with recursion Java Solution, faster than 55%


  • 0

    Main idea:

    • Backtracking with recursion
    • Edge case: num>255, too many digits, too few digits, the last dot in IP address.

    Attached is the AC code:

    public class Solution {
      List<String> ret;
      public List<String> restoreIpAddresses(String s) {
        ret = new ArrayList<String>();
        if(s.length()>12) return ret;
        helper(1,"", s);
        return ret;
      }
      private void helper(int level, String res, String rem){
        // Valid IP address
        if(level==5 && rem.length()==0) ret.add(res);
        // Invalid IP address, too much, not sufficient
        if(level==5 && rem.length()!=0) return;
        if(rem.length()==0) return;
        
        for(int i=0;i<3 && i<rem.length();i++){
          if(Integer.valueOf(rem.substring(0,i+1))>255) return;
          // handle the last dot in IP address
          if(level==4) helper(level+1, res+rem.substring(0,i+1), rem.length()>i+1?rem.substring(i+1):"");
          else helper(level+1, res+rem.substring(0,i+1)+".", rem.length()>i+1?rem.substring(i+1):"");
          / /handle 0 in IP address
          if(rem.charAt(0)=='0') break;
        }
      }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.