Java 3ms backtracking solution without transfering String to Integer


  • 0
    T
    public class Solution {
    public List<String> restoreIpAddresses(String s) {
       	List<String> mylist = new ArrayList<String>();
    	int[] pos={0,0,0,0,s.length()}; //initial pos array, put 0 in pos[0], str.length() in pos(4)
    	backtracking(mylist,1,pos,s,0);
    	return mylist;
    	
    }
    
    public static void backtracking(List<String> myList,int currDivision, int[] pos,String str,int head){
    
    	if(currDivision==4){ //when reachs the last division
    		if(pos[3]<pos[4]-3 || pos[3]>pos[4]-1) // division wrong
    			return;
    			
    		for(int i=1;i<pos.length;i++){
    			if((pos[i]-pos[i-1]==3) && str.substring(pos[i-1],pos[i]).compareTo("255")>0 ) //digits out of range
    				return;		
    			if((pos[i]-pos[i-1]>1) && str.charAt(pos[i-1])=='0') //double zero in one division
    				return;		
    		}
    
    		String newIP = str.substring(pos[0], pos[1])+"."+str.substring(pos[1],pos[2])+"."+str.substring(pos[2],pos[3])+"."+str.substring(pos[3],pos[4]);
    		myList.add(newIP);
    		return;
    	}
    	for(int i=Math.min(head+3, str.length());i>=head+1;i--){
    		pos[currDivision]=i; //put the start position of each division into pos array [1-3]
    		backtracking(myList,currDivision+1,pos,str,i);
    	}
    }
    

    }


Log in to reply
 

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