Simple Java Backtracking Solution


  • 0
    V
    In this solution backtracking is used. For adding substring to the IP address we need to check following two cases:
     1. It should be less than or equal to 255.
     2. We need to use all elements, so length of converted value should be same as length of substring.
    Example "10" = 10 and it can be added but "010" = 10 and it can't be added as we will miss one 0 in the result.
    
    public List<String> restoreIpAddresses(String s) {
    	List<String> result = new ArrayList<>();
    	if (s.length() > 12)
    		return result;
    	return restoreIPAddressHelper(s, 4);
    }
    
    List<String> restoreIPAddressHelper(String s, int iter) {
    	List<String> result = new ArrayList<>();
    	
    	if (iter == 1) {
    		long value = Long.parseLong(s);
    		if (String.valueOf(value).length() == s.length() && value <= 255)
    			result.add(value + "");
    	}
    	else {
    		for (int i = 0; i < s.length() - iter + 1; i++) {
    			long curValue = Long.parseLong(s.substring(0, i + 1));
    			if ( String.valueOf(curValue).length() == i + 1 && curValue <= 255) {
    				List<String> temp = restoreIPAddressHelper(
    						s.substring(i + 1), iter - 1);
    				if (!temp.isEmpty()) {
    					for (String prevString : temp) {
    						result.add(curValue + "." + prevString);
    					}
    				}
    			}
    		}
    	}
    	return result;
    }

Log in to reply
 

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