（回溯法）Java 求解复原 IP 地址

旧城等待， 2023-01-19 12:53 36阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、回溯分析
     *  三、代码
     *  四、总结

## 一、题目 ##

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 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 地址。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、回溯分析 ##

该题和 [分割回文串][Link 1] 类似，也可以看作是组合问题，然后判定每个子字符串是否符合要求

（1）确定递归参数

> 因为符合条件的子字符串需要给其加 `"."`，回溯时，也需要删除这个 `"."`，所以采用 StringBuilder 来操作  
> 需要的参数有，字符串s，切割的起始下标 startIndex（防止重复），记录添加逗点的pointNum

（2）递归终止条件

> 当`pointNum==3`时，表示IP地址组成，此时需要判断第四段也就是`(startIndex,sb.length()-1)`是否符合要求，符合则进行记录

//逗号数量为3时，结束分隔
    if (pointNum == 3) { 
        //判断第四段子字符串是否合法
        if (isValid(sb.toString(), startIndex, sb.length() - 1)) { 
            list.add(sb.toString());
        }
    }

（3）确定回溯搜索过程

> startIndex 表示下一轮递归遍历的起始位置，也可以看作切割线  
> 在`for (int i = startIndex; i < s.length(); i++)`循环中，我们 定义了起始位置`startIndex`，那么 `[startIndex, i]` 就是要截取的子串  
> 判断这个子串是否符合要求

判断是否符合要求：

> IP段为0开头的数字不合法  
> IP段有非正整数字符不合法  
> IP段大于255不合法

//判断子字符串是否合法
    private boolean isValid(String s, int start, int end) { 
        if (start > end) { 
            return false;
        }
        //0开头的数字不合法
        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;
            }
            num = num * 10 + s.charAt(i) - '0';
            if (num > 255) { 
                return false;
            }
        }
        return true;
    }

## 三、代码 ##

class Solution { 
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
    
        public List<String> restoreIpAddresses(String s) { 
            //长度不够，或者超出范围直接返回
            if (s.length() < 4 || s.length() > 12) { 
                return list;
            }
            //方便操作，将 String 转为 StringBuilder
            sb.append(s);
            backTracking(sb, 0, 0);
            return list;
        }
    
        private void backTracking(StringBuilder sb, int startIndex, int pointNum) { 
            //逗号数量为3时，结束分隔
            if (pointNum == 3) { 
                //判断第四段子字符串是否合法
                if (isValid(sb.toString(), startIndex, sb.length() - 1)) { 
                    list.add(sb.toString());
                }
            }
            for (int i = startIndex; i < sb.length(); i++) { 
                if (isValid(sb.toString(), startIndex, i)) { 
                    //在i的后面插入一个逗点
                    sb.insert(i + 1, ".");
                    //插入逗点后，下一个子串的起始位置为i+2
                    backTracking(sb, i + 2, ++pointNum);
                    //回溯删掉逗点
                    pointNum--;
                    sb.deleteCharAt(i + 1);
                } else { 
                    break;
                }
            }
        }
        //判断子字符串是否合法
        private boolean isValid(String s, int start, int end) { 
            if (start > end) { 
                return false;
            }
            //0开头的数字不合法
            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;
                }
                num = num * 10 + s.charAt(i) - '0';
                if (num > 255) { 
                    return false;
                }
            }
            return true;
        }
    }

## 四、总结 ##

同切割问题，类似组合，需要对每一种组合进行判断是否符合要求

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221021/8e28f5462db14832bf1e1286447a3844.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/116572372