My concise AC java code


  • 33

    the basic idea is to make three cuts into the string, separating it into four parts, each part contains 1~3 digits and it must be <255.

    static List<String> restoreIpAddresses(String s) {
    	List<String> ans = new ArrayList<String>();
    	int len = s.length();
    	for (int i = 1; i <=3; ++i){  // first cut
    		if (len-i > 9) continue;    		
    		for (int j = i+1; j<=i+3; ++j){  //second cut
    			if (len-j > 6) continue;    			
    			for (int k = j+1; k<=j+3 && k<len; ++k){  // third cut
    				int a,b,c,d;                // the four int's seperated by "."
    				a = Integer.parseInt(s.substring(0,i));  
    				b = Integer.parseInt(s.substring(i,j)); // notice that "01" can be parsed into 1. Need to deal with that later.
    				c = Integer.parseInt(s.substring(j,k));
    				d = Integer.parseInt(s.substring(k));
    				if (a>255 || b>255 || c>255 || d>255) continue; 
    				String ip = a+"."+b+"."+c+"."+d;
    				if (ip.length()<len+3) continue;  // this is to reject those int's parsed from "01" or "00"-like substrings
    				ans.add(ip);
    			}
    		}
    	}
    	return ans;
    }

  • 0
    X
    if (ip.length()<len+3) continue; 
    

    This is very smart check!


Log in to reply
 

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