93. 复原IP地址

93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

class Solution {
    public List<String> restoreIpAddresses(String s) {
        //点的个数、index
        List<String> res = new ArrayList<>();
        if(s == null || s.length() < 4) return res;
        bt(s,0,4,res,"");
        return res;
        
    }
    private void bt(String s,int index,int flag,List<String> list,String str){
        if(index == s.length() &&flag == 0){
            //去掉最后一个点
            list.add(str.substring(0,str.length() - 1));
        }
        if(flag < 0) return;
        //注意i的边界
        for(int i = index;i < index + 3;i++){
            if(i >= s.length()) break;
            //第一个为0，单独占一个flag
            if(i == index && s.charAt(i) == '0'){
                bt(s,i + 1,flag - 1,list,str + "0.");
                //不用继续，直接退出循环
                break;
            }
            //在255以内
            if((Integer.parseInt(s.substring(index,i + 1)) <= 255)){
                bt(s,i + 1,flag - 1,list,str + s.substring(index,i + 1) + ".");
            }
        }
        
    }
}