Simple Java Solution Beating 100% of Java submissions


  • 4
    A
    /*Description of variables
    result - list of valid ip addr strings
    digits -char array representation of s
    len - length of s
    currIpAddr - char array that contains the IP addr we are building using backtracking
    remSegs - no. of segments remaining to be parsed. there 4 segments to an ip addr
    start - start index in the digits array for the current ip addr segment
    pos - next index to be populated in the currIpAddr array
    
    */
    
    public class Solution {
    
    private static final char DOT = '.';
    
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        
        char[] digits = s.toCharArray();
        int len = s.length();
        char[] currIpAddr = new char[len+3];
        int pos = 0;
        generateIpAddresses(digits, 4, 0, len, currIpAddr, pos, result);
        
        return result;
    }
    
    private void generateIpAddresses(char[] digits, int remSegs, int start, int len, 
                                     char[] currIpAddr, int pos, List<String> result) {
            if(start == len && remSegs == 0) {
                result.add(String.valueOf(currIpAddr));
                return;
            }   
        
       //1. Checks for length of s too small
       //2. Maximum Length of the remaining segments. Since a sgemnt can be upto 3 digits
       // Length can not exceed 3x the remaining segments.
       //3. Minimum Length of s. Each segment has to be atleast 1 digit
        if((start > len) || ((len - start) > (3 * remSegs)) || ((len - start) < remSegs))
            return;
        
        if(remSegs < 4)
            currIpAddr[pos++] = DOT;
        
        int num = 0;
        
        for(int i = 0; i < Math.min(len-start, 3);i++) {
            num = (10*num) + (int)(digits[start+i] - '0');
            
            if(i > 0 && num < 10)// leading 0 cases i = 1, then the number should be > 10.
                return;
            
            ////"010010"
            //Valid: ["0.10.0.10","0.100.1.0"]
            //Invalid: ["0.1.0.010","0.1.00.10","0.1.001.0","0.10.0.10","0.10.01.0","0.100.1.0",
            //"01.0.0.10","01.0.01.0","01.00.1.0","010.0.1.0"]
            
            if(num <= 255) {
                currIpAddr[pos+i] = digits[start+i];
                generateIpAddresses(digits, remSegs-1, start+i+1, len, currIpAddr, pos+i+1, result);
            }
        }
      }    
    }

  • 1
    G

    Excellent solution!



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