7.7复原IP地址（LC93-M）

算法：

根据题意

有效的 IP 地址 ：

（1）由四个整数构成

（2）每个整数位于 0 到 255 之间

（3）每个整数不能含有前导 0，如011、021等，但是可以有单独的一个“0”

（4）整数之间用 '.' 分隔。

其实本质上就是分割问题，把一串数字分成四部分，每部分要满足条件（2）和（3），这四个部分用字符'.'串起来，所以还是用回溯

画树：

回溯三部曲：

1.确定函数返回值和参数

返回值：void

参数：

String s（题目自带）

int startindex：记录下一层递归分割的起始位置。

Int?pointNum；记录添加“.”的数量（要加3个）

2. 确认终止条件，收集合法的数字段：

本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。

3.单层递归逻辑：

for循环：

//收集结果

for (int i = startIndex; i < s.length(); i++)

[startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环

//递归

同时记录分割符的数量pointNum 要 +1

backtracking(s, i+2, pointNum)

i+2，可以看下图：

i=3时，下一层递归的startindex=5

//回溯

pointNum要-1

将刚刚加入的分隔符.?删掉

判断子串是否合法

主要考虑到如下三点：

• 段位以0为开头的数字不合法
• 段位里有非正整数字符不合法
• 段位如果大于255了不合法

判断时遵循“左闭右闭”

先判错

注意：

1.这里的全局变量没有path了

因为result就是一个一维数组，数组由字符串构成

什么时候需要path?

result为二维数组时，比如

正确代码：

class Solution {
    //全局变量result
    List<String> result = new LinkedList<>();
    
    public List<String> restoreIpAddresses(String s) {
        if (s.length()>12) return result;
        baktracking (s, 0, 0);
        return result;

    }
    void baktracking (String s, int startindex, int pointNum){
    //确定终止条件，收集结果
    if (pointNum == 3) {
    //判断第三个"."之后的第四段字段是否合法（前三段在单层递归逻辑中判断是否合法）
    //若合法，则将该合法字符s加入reslt
    //索引从0开始
    if (isvalid (s, startindex, s.length()-1)){
        result.add(s);
    }
    return;}
    //单层递归逻辑
    for (int i= startindex; i< s.length(); i++){
        //判断是否合法，合法就加"."
        if (isvalid (s, startindex, i)) {
        //因为string不可变，所以要重新赋值给一个新的string
        s = s.substring(0, i+1)+"."+s.substring(i+1);
        //substring左闭右开，所以两个都是i+1
        pointNum++;
        //递归
        baktracking (s, i+2, pointNum);
        //回溯
        pointNum--;
        //因为string不可变，所以要重新赋值给一个新的string
        s = s.substring(0, i+1)+s.substring(i+2);
        //第二个substring从i+2开始，因为前面有个“.”      
        }
        else break;
    }

    }

   
    //判断字符串是否合法，左闭右闭
    //先判错
    //1.每位是正整数，在0-9(题目说s 仅由数字组成)
    //2.每个整数位于 0 到 255 之间
    //3.不能含有前导 0
    boolean isvalid (String s, int start, int end) {
        //if (s.length()>12) return false;这里不能写这句话，因为S里面可能有“.”，确实不止12
        if (start > end) return false;
        int num = 0;
        for (int i= start; i<=end ;i++){
            if (s.charAt(i) < '0' || s.charAt(i) > '9') return false;
            num = num*10+ (s.charAt(i)-'0');
            if (num > 255) return false;
        }
        if (s.charAt(start) == '0' && start != end) return false;
        return true;
    }
}

优化：

由于string不能直接改，每次都要赋值个新的s，比较占空间；可以使用stringBuilder

优化后的正确代码：

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backTracking(sb, 0, 0);
        return result;
    }
    private void backTracking(StringBuilder s, int startIndex, int dotCount){
        if(dotCount == 3){
            if(isValid(s, startIndex, s.length() - 1)){
                result.add(s.toString());
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s, startIndex, i)){
                s.insert(i + 1, '.');
                backTracking(s, i + 2, dotCount + 1);
                s.deleteCharAt(i + 1);
            }else{
                break;
            }
        }
    }
    //[start, end]
    private boolean isValid(StringBuilder s, int start, int end){
        if(start > end)
            return false;
        if(s.charAt(start) == '0' && start != end)
            return false;
        int num = 0;
        for(int i = start; i <= end; i++){
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255)
                return false;
        }
        return true;
    }
}

时间空间复杂度：