(回溯) LeetCode 93. 复原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 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

1 <= s.length <= 20
s 仅由数字组成

二. 解题思路

IP地址相信大家十分熟悉了吧，合法的IP地址就是：（1）在IP之内除了数字不存在其他字母或者字符；（2）每两个点号的之间的数字不能以0开头(0除外)；（3）每两个点号的之间的数字不能超过255。

1. 上面提到的三个判断是否合法的条件，第一个题目中明确说只有数字组成，所以只需要考虑后面两个条件即可，我们这里通过一个isvalid 函数判断是否合法，具体写法在下面的代码中有，这里不做多的赘述。

2. 又到了我们熟悉的环节，第一，确定递归条件：在这里我们首先需要传入字符串s ，再有就是切割位置startindex ，还有一个就是加入的分割点的点数pointnum，至于这个对后面的判断递归终止条件有作用。

3. 第二，递归终止条件：上面说到有个pointnum ，这个就是判断是否退出递归的必要条件，IP地址中间的点数想必大家都很清除，有三个，所以当我们判断如果pointnum == 3 的时候，就可以退出递归了，不过在退出递归之前要收集结果，在收集结果之前也必须做一步判断，因为在单层递归的时候都是对切割位置前面的进行合法性判断，在最后一次切割之后，字符串末尾还有几位需要进行合法性判断，在判断合法之后就可以将其收集了。

4. 第三，单层递归：从startindex 位置开始，每一层循环判断一下切割是否合法，如果合法，就在其后面加一位点号，再将pointnum 加1，再进行递归，以往我们递归的时候会从第i + 1 位开始，但是由于刚才在字符串中添加了点号，所以就得后移一位，从i + 2 ，开始递归。

5. 第四，回溯：在递归返回之后，需要将之前修改的值复原，方便下一层的循环递归。

话不多说！！！上代码！！

三. 代码

class Solution {
public:vector<string> res;                      // 收集结果 bool isvalid(string s, int l, int r){   // 判断切割的子串是否合法if(l > r) return false;if(s[l] == '0' && l != r) return false;int num = 0;for(int i = l; i <= r; i++){num = num * 10 + (s[i] - '0');if(num < 0 || num > 255) return false;}return true;}void back(string s, int startindex, int pointnum){if(pointnum == 3){if(isvalid(s, startindex, s.size() - 1)){       // 需要判断切割之后结尾的几位是否合法res.push_back(s);}return;}for(int i = startindex; i < s.size(); i++){if(isvalid(s, startindex, i)){s.insert(s.begin() + i + 1, '.');pointnum++;back(s, i + 2, pointnum);       // 因为合法之后会添加一个点号作为分割，所以得从i + 2 开始pointnum--;s.erase(s.begin() + i + 1);}else break;                        // 如果当前切割的位置不合法，后面就没有必要再判断了，必定不合法}}vector<string> restoreIpAddresses(string s) {back(s, 0, 0);return res;}
};