Alg.15 Valid IP Addresses

From algoexpert.io

Given a string of length 12 or smaller, consists of only digits. We need to write a function to find out all the potential IP addresses by inserting 3 ‘.’ to each address. In the code implementation, we simply iterate the original string and enumerate all the combinations. The key part is how we design a function to recognize a valid IP addess.

public boolean isValid(String string) {
        int num = Integer.parseInt(string);
        if (num > 255) return false;
        return string.equals(Integer.toString(num));
    }

In this ‘isValid’ function, we return ‘string.equals(Integer.toString(num))’ in order to avoid situations like ‘01’, ‘001’, ‘00’, etc. If we find a valid IP, we have to build up the result.

public String join(String[] validIp) {
        StringBuilder sb = new StringBuilder();
        sb.append(validIp[0]);
        for (int i = 1; i < validIp.length; i++) {
            sb.append('.');
            sb.append(validIp[i]);
        }
        
        return sb.toString();
    }

Now, we can do our iteration and enumerate all the combinations.

public ArrayList<String> validIPAddresses(String string) {
        ArrayList<String> ans = new ArrayList<String>();
        int len = string.length();
        if (len < 4) return ans;
        for (int i = 1; i < Math.min(len, 4); i++){
            String[] validIp = new String[]{"", "", "", ""};
            validIp[0] = string.substring(0, i);
            if (!isValid(validIp[0])) continue;
            
            for (int j = i + 1; j < i + Math.min(len - i, 4); j++) {
                validIp[1] = string.substring(i, j);
                if (!isValid(validIp[1])) continue;
                
                for (int k = j + 1; k < j + Math.min(len - j, 4); k++) {
                    validIp[2] = string.substring(j, k);
                    validIp[3] = string.substring(k);
                    
                    if (isValid(validIp[2]) && isValid(validIp[3])) {
                        ans.add(join(validIp));
                    }
                }
            }
        }
    return ans;
  }

Time complexity: O(1); Space complexity: O(1)

Donate