[网络协议]【回溯算法】【打卡第187道】：leetCode :93. 复原 IP 地址

1、题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入?'.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

2、算法分析

本题是典型的分割问题，属于回溯算法中的一种。

注意：在IP分段地址中，只能包含数字，且数字的范围是0—9之间，IP地址范围是0—255之间

①首先确定回溯函数

void 返回值，backTracking是回溯函数，回溯函数中的参数是：

String?s,int?startIndex,int?num

startIndex防止重复切割，num计数点的数量。

②确定递归结束条件

也就是说，当num == 3的时候，且最后一段IP地址符合条件的时候，结束递归条件。

③单层搜索

注意isValid(s,startIndex,i)：判断IP段是否是0--255之间的

backTracking(s,i+2,num)：i+2是有 点 . 所以i+2

回溯的话，num--，s.substring(0,,i+1) + s.substring(i+2)；

?

本题确实比较难理解，难就难在怎么分割，IP中间的.怎么处理。

这一题还有上一题，都属于hard，慢慢理解。

3、代码实现

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length() > 12){
            return res;
        }
        backTracking(s,0,0);
        return res;
    }

    // startIndex不能重复切割，num代表的是逗号的数量
    public void backTracking(String s,int startIndex,int num){
        
        // 说明有3个逗号了，还剩下最后一个IP地址中最后一个子地址
        if(num == 3){
            //判断第四段字符串是否合法
            if(isValid(s,startIndex,s.length() - 1)){
                res.add(s);
            }
            return;
        }

        // 单层搜索
        for(int i = startIndex;i < s.length();i++){
            if(isValid(s,startIndex,i)){
                s = s.substring(0,i + 1) + "." + s.substring(i + 1);
                num++;
                backTracking(s,i+2,num);
                // 回溯
                num--;
                // 去掉逗号
                s = s.substring(0,i + 1) + s.substring(i + 2);
            }else{
                break;
            }

        }
    }

    // 判断字符串在区间范围内,是否合法；判断范围内的，127.0.0.1，范围内的比如说127，判断IP地址的每一位！
    public boolean isValid(String s,int start,int end){
        if(start > end){
            return false;
        }

        //开始是0的，不符合条件 010.1000.100.100
        if(s.charAt(start) == '0' && start != end){
            return false;
        }
        
        int num = 0;
        for(int i = start;i <= end;i++){
            // 去除非数字的部分
            if(s.charAt(i) > '9' || s.charAt(i) < '0'){
                return false;
            }
            // 每一个位上的，s.charAt(i)-'0'：两个字符相减实际上是ASCII码对应的数相减;返回的是十进制的值
            num = num * 10 + (s.charAt(i) - '0');
            if(num > 255){
                return false;
            }
        }
        return true;
    }
}