Question:

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)

Thinking:

Valid IP address is between 0 and 255, so we can once detect one to three digits of the string. What’s more, it’s not valid if there is number like “001”. Use bactracing select one to three digits once, and go farther until all the substrings are selected and there are four parts of the result. Then put the result in the list. We should also detect the length of the String because if the length is not between 4 and 12, it’s invalid.

Solution:

public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<String>();

    if (s.length() < 4)
        return res;
    if (s.length() > 12)
        return res;

    backtracing(s, 0, new ArrayList<String>(), res);

    return res;
}

public void backtracing(String s, int start, List<String> tempres, List<String> res){
    if (start == s.length()){
        if (tempres.size() == 4){
            String tempstr = "";
            tempstr = tempres.get(0) + "." + tempres.get(1) + "." + tempres.get(2) + "." + tempres.get(3);
            res.add(tempstr);
        }
        else{
            return;
        }
    }

    for (int i = start+1; i <= s.length(); i++){
        if (s.charAt(start) == '0' && i != start+1)
            continue;
        if (i - start > 3)
            break;
        int num = Integer.parseInt(s.substring(start, i));
        if (num > 255)
            break;
        else{
            tempres.add(s.substring(start, i));
            backtracing(s, i, tempres, res);
            tempres.remove(tempres.size() - 1);
        }
    }
}