Java 3ms recursive solution


  • 0

    Simply. you can get first 1-3 characters, if they yield a valid IP sub part (number between 0-255, no extra 0), then find valid suffix from rest of the string. Recurse.
    Since IP address can have only 4 parts, limit to four levels, where we add resulting IP addresses to resulting list at 4th level.

    public class RestoreIPAddresses {
    	public List<String> restoreIpAddresses(String s) {
    		List<String> list = new ArrayList<>();
    		restoreIp("", s.toCharArray(), 0, list, 0);
    		return list;
    	}
    	
    	private void restoreIp(String prefix, char[] chars, int start, List<String> list, int level) {
    		if (start >= chars.length) {
    			return;
    		}
    		if ((chars.length - start) <= 3 && level == 3) {
    			String finalPart = new String(chars, start, (chars.length - start));
    			if(validIpDigits(finalPart)){
    				list.add(prefix + finalPart);
    			}
    		}
    		if(level<3) {
    			for (int i = 1; i <= 3 && i < (chars.length - start); i++) {
    				String newPart = new String(chars, start, i);
    				if(validIpDigits(newPart)) {
    					restoreIp(prefix + newPart + ".", chars, start + i, list,
    							level + 1);
    				}
    			}
    		}
    	}
    	
    	private static boolean validIpDigits(String s){
    		Integer val = Integer.valueOf(s);
    		return (val==0 && s.length()==1) || (val>0 && val<256 && s.charAt(0)!='0');
    	}
    	
    	public static void main(String[] args) {
    		System.out.println(new RestoreIPAddresses().restoreIpAddresses("010010"));
    	}
    }
    

Log in to reply
 

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