复原IP地址

题目：力扣

解题思路：

这道题的难点在于剪枝的情况比较多，可能考虑不全。

class Solution {
    List<String> res = new LinkedList<>();
    int min_len = 1;
    int max_len = 3;
    public List<String> restoreIpAddresses(String s) {
        if(s.length()<4 || s.length() >12){
            return res;
        }
        if(s.length() == 4){
            min_len = 1;
            max_len = 1;
        }
        if(s.length() == 5){
            min_len = 1;
            max_len = 2;
        }
        if(s.length() == 11){
            min_len = 2;
            max_len = 3;
        }
        if(s.length() == 12){
            min_len = 3;
            max_len = 3;
        }
        StringBuffer route = new StringBuffer();
        backtrace(route, s, 0, 0);
        return res;

    }
    public void backtrace(StringBuffer route, String choice, int start, int nums){
        if(choice.length()-start > 3*(4-nums) || start > choice.length()){
            return;
        }
        if(start == choice.length() && nums == 4){
            res.add(route.toString());
            return;
        }
        for(int i = min_len; i <= max_len; i++){
            if(start+i > choice.length()){
                break;
            }
            String cur = choice.substring(start, start+i);
            if(Integer.parseInt(cur)>255 || (Integer.parseInt(cur)!= 0 && cur.charAt(0) =='0') ||(Integer.parseInt(cur)== 0 && cur.length() > 1)){
                break;
            }
            route.append(cur);
            if(nums<3)
                route.append('.');
            backtrace(route, choice, start+i, nums+1);
            if(nums<3)
                route.delete(route.length()-1, route.length());
            route.delete(route.length()-i, route.length());
        }
    }
}