算法通关18关 | 回溯模板如何解决复原IP问题

        18关的前几篇文章看过之后，对回溯的模板问题基本解题思路就知道了，就是固定的for循环问题，外层for循环控制横向，递归控制纵向，还要考虑撤销操作和元素是否能被重复利用问题，重复利用的情景较少，只用注意撤销就行。

1. 复原IP地址

题目

经典题目，LeetCode93 有效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 中的任何数字。你可以按 任何 顺序返回答案。

思路

写一个单独的方法来判断每个部分是否符合要求，

IP地址最多有4段，所以4也就是终止条件，因为需要手动添加小数点，用pointNum来表示小数点的数量，pointNum=3说明被分成4段。手动添加小数点，这要增加一个位置来存储，所以下一层递归startindex就要从i + 1，开始，其他的就是递归和回溯的过程，撤销就是将刚刚加入的分隔符删掉，并且pointNum也要减1，

代码

    public Boolean isVaild(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;}List<String> result = new ArrayList<>();public List<String> restoreIPAddress(String s){//这个是ip特性决定的if (s.length() < 4 || s.length() > 12){return result;}backTrack(s,0,0);return result;}private void backTrack(String s, int startIndex, int pointNum) {if (pointNum == 3){//小数点为3时候，分割结束，//判断第四段是否合法，合法放入resul中if (isVaild(s,startIndex,s.length() - 1)){result.add(s);}return;}for (int i = startIndex; i < s.length(); i++) {if (isVaild(s,startIndex,i)) {//后面插入小数点s = s.substring(0, i + 1) + "." + s.substring(i + 1);pointNum++;//插入小数点之后下个位置的起始字符位置i+2backTrack(s, i + 2, pointNum);pointNum--;//撤销操作s = s.substring(0, i + 1) + s.substring(i + 2);//撤销小数点}else {break;}}}