93. Restore IP Addresses

/**
 * Time Complexity : O(3^3 * N) = O(N)
 *
 * For every i, j runs thrice. For every j, k runs thrice. Thus for every i, k
 * runs 3*3 times. Since i runs thrice too, all for loops will run for 3*3*3
 * times.
 *
 * Space Complexity: O(N) .. This is required for Substring
 *
 * N = Length of the input string
 */
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return result;
        }

        int strLen = s.length();

        for (int i = 1; i < 4 && i < strLen - 2; i++) {
            for (int j = i + 1; j < i + 4 && j < strLen - 1; j++) {
                for (int k = j + 1; k < j + 4 && k < strLen; k++) {
                    String octet1 = s.substring(0, i);
                    String octet2 = s.substring(i, j);
                    String octet3 = s.substring(j, k);
                    String octet4 = s.substring(k, strLen);
                    if (isValidOctet(octet1) && isValidOctet(octet2) && isValidOctet(octet3) && isValidOctet(octet4)) {
                        result.add(octet1 + "." + octet2 + "." + octet3 + "." + octet4);
                    }
                }
            }
        }
        return result;
    }

    private boolean isValidOctet(String o) {
        if (o.length() == 0 || o.length() > 3 || (o.length() > 1 && o.charAt(0) == '0') || Integer.parseInt(o) > 255) {
            return false;
        }
        return true;
    }
}