Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

since ip address can be at most be 4 parts, use an array of length 4 to store each part.

use bruteforce recursion check each element in the string to see if the whole string can be composed as a valid ip address.

valid ip:

• if starts with 0, must be 0
• must be greater than 0 and less than or equal to 26

public List<String> restoreIpAddresses(String s) {
        List<String> results = new ArrayList<String>();
        String[] curr = new String[4];
        restore(s, 0, curr, results);
        return results;
    }

    private void restore(String s, int level, String[] curr, List<String> result) {
        if (level == curr.length) {
            //if s is not empty, don't add.
            if (s.isEmpty()) {
                result.add(convertToIpString(curr));
            }
            return;
        }

        for (int i = 1; i<Math.min(curr.length, s.length()+1); i++) {
            String left = s.substring(0, i);
            String right = s.substring(i);
            if (isValid(left)) {
                curr[level] = left;
                restore(right, level + 1, curr, result);
            }
        }

    }

    private String convertToIpString(String[] curr) {
        StringBuilder sb = new StringBuilder();
        for (String s : curr) {
            sb.append(s);
            sb.append(".");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public boolean isValid(String s) {
        if (s.startsWith("0")) {
            return s.length()==1;
        }
        int num = Integer.parseInt(s);
        return num <= 255 && num >= 0;
    }