LeetCode - Restore IP Addresses

Question Definition

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)

Java Solution

public List<String> restoreIpAddresses(String s) {
    List<String> result = new LinkedList<>();
    if(s.length() == 0 || s.length() > 12) return result;
    restoreIpAddressesHelper(s, 0, 4, "", result);
    return result;
}

private void restoreIpAddressesHelper(String s, int start, int num, String cur, List<String> result){
    if(num == 0 && start == s.length()){
        cur = cur.substring(0, cur.length() - 1);
        result.add(cur);
        return;
    }

    for(int i = start + 1; i <= s.length(); i++){
        String sub = s.substring(start, i);
        int digit = Integer.parseInt(sub);
        if(digit > 255) break;
        restoreIpAddressesHelper(s, i, num - 1, cur + sub + ".", result);
        if(digit == 0) break;
    }
}

Comments