Leetcode 93 复原 IP 地址

题意理解：

? ? ? ? 首先明确什么是正确的IP地址：简单理解三个小数点分割四个数字，每个数字的大小应在[0,255]内，且合法的数字表示不应该以0开头。

? ? ? ? 合法：0.1.2.201? ? ? ? ? ? ? ? ? ? ? ? 不合法：0.01.2.257

? ? ? ? 我们需要再合适的位置添加小数点。小数点总是添加在数字之间的位置。

解题思路：

? ? ? ? 如何在合适的位置添加小数点。

? ? ? ? 其和切割字符串以满足某种要求的题目是类似的。这一类的题都可以用回溯的方法解决。

? ? ? ? 约束条件则对应在合适的地方做剪枝操作，以便收集正确的结果。

1.暴力回溯+剪枝优化

前期准备： 判断数字是合法的ip的一部分，即数字在[0,255内]，且不以0开头。

回溯解决问题三个关键步骤：????????

? ? ? ? 1.确定返回值+参数列表

? ? ? ? 2.确定终止条件：获得三个小数点时，即可终止，因为合法的ip地址只有四段。

? ? ? ? 3.单层逻辑|递归

? ? ? ? 注意：

1. ????????插入小数点的位置总是当前位置的后面，即cur+1的位置
2. ? ? ? ? 下一层递归开始的位置是i+2: 即挪到下一个数字，且因为加入小数点多了一位，故因再往后挪一位，即+2。
3. ????????10.10.23.? ?时，判断是否是ip时，坐标超出范围，返回false
4. ? ? ? ? 数值越界问题：三个小数点后的数字串，应该再[0,255]之间，所以其长度超过3就可以返回false了，否则，再与0和255 比较，判断是否合法，如果直接转int或long, 过长的数字串可能导致数值越界。

  List<String> result=new ArrayList<>();
    //记录小数点个数
    int pointNum=0;
    StringBuilder s=new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        backtracking(new StringBuilder(s),0);
        return result;
    }
    //回溯|递归方法
    public void backtracking(StringBuilder s,int startIndex){
        //终止条件
        if(pointNum==3){
            if(isIPNumber(s,startIndex,s.length()-1)){
                //合法的子串
                result.add(new String(s));
            }
            return;
        }
        //单层递归逻辑
        for(int i=startIndex;i<s.length();i++){
            if(isIPNumber(s,startIndex,i)){
                s.insert(i+1,'.');
                pointNum++;
                backtracking(s,i+2);
                s.deleteCharAt(i+1);
                pointNum--;
            }else{
                continue;
            }
        }

    }
    //是合法ip数字,左闭右闭
    public boolean isIPNumber(StringBuilder s,int start,int end){
        //控制数组越界问题
        if(start>=s.length()) return false;
        if(s.charAt(start)=='0'&&start!=end) return false;
        //控制数值问题
        if(s.substring(start,end+1).length()>3) return false;
        int sNum= new Integer(s.substring(start,end+1));
        if(sNum<0||sNum>255) return false;
        return true;
    }

2.分析

时间复杂度：O()

空间复杂度：O(SEG_COUNT)

?SEG_COUNT=4 表示 IP 地址的段数,S_LEN是字符串长度