93. 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)

解题思路为backtracking。

需要将string中间加三个点，分成四部分。先确定一部分，然后对剩下的子串进行递归，直到分成四部分，如果valid，则添加至res中。

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length() < 4 || s.length() > 12) return res;
        helper(s, 3, res, "");
        return res;
    }
    
    private void helper(String s, int dot, List<String> res, String ip) {
        if(dot == 0) {
            if(isValid(s)) {
                ip += s;
                res.add(ip);
            }
            return;
        }
        for(int i = 1; i < 4 && i < s.length(); i++) {
            String str = s.substring(0, i);
            if(isValid(str)) {
                helper(s.substring(i), dot-1, res, ip + str + ".");
            }
        }
    }
    
    private boolean isValid(String s) {
        if(s.startsWith("0") && s.length() > 1 || Integer.valueOf(s) > 255) return false;
        return true;
    }
}