How to generate all the valid IP Addresses from a String of number

08/22/2019

Generating the valid IP addresses from a String is a classic interview question. It is done using back tracking and a utility method that test is the current subString is a valid digit.

The main method loops on the characters of the input String. If the subString is a valid character, it remembers it and calls itself searching for n-1 characters. If at any point no characters are available or the sub String is not a valid digit, then the process stops.

Create the following java file:

import java.util.ArrayList;
import java.util.List;

public class InterviewValidIP {

    public ArrayList<String> restoreIpAddresses(String A) {
        ArrayList<String> toReturn = new ArrayList<String>();
        if( A == null )
            return toReturn;
            
        process(toReturn, "", A, 4);
        
        return toReturn;
    }
    
    public void process(ArrayList<String> toReturn, String tmpIP, 
        String in, int remaining){
        
        if( remaining == 0 && in.length() == 0 ) {
            toReturn.add( tmpIP );
            return;
        }
        
        for( int i = 1 ; i <= in.length() ; i++ ){
            String tmp = in.substring(0, i);
            
            if( !isValidDigit(tmp) ){
        	return;
            }

            StringBuilder updatedIP = new StringBuilder();
            updatedIP.append( tmpIP );
            if ( tmpIP.length() != 0 )
        	updatedIP.append( "." );
                	
            updatedIP.append( tmp );

            String remainder = in.substring( i, in.length() );
            
            int lessOne = remaining - 1;
            process( toReturn, updatedIP.toString(), remainder, lessOne);
        }
    }
    
    public boolean isValidDigit(String in){
        int i = -1;
        try { i = Integer.parseInt( in ); }catch(Exception e){}
        
        if( i == -1  )
            return false;
        if( i != 0 && in.charAt(0) == '0' )
            return false;

        if( i == 0 && in.charAt(0) == '0' && in.length() != 1 )
            return false;
            
        
        return i >= 0 && i <= 255;
    }

    public static void main(String[] argv) throws Exception {
	InterviewValidIP t = new InterviewValidIP();

	List<String> out = t.restoreIpAddresses( "0100100" );
	
	for(String c : out){
	    System.out.println( "found=" + c );
	}
    }

}

The output will be:

found=0.10.0.100
found=0.100.10.0

The utility method is called isValidDigit, it validate that the number is a valid integer that is positive and less that 256. It also check that the number doesn't start with 0 if it's not 0.

References:

IP address