本文主要是介绍【回溯算法】【打卡第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.100if(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;}
}这篇关于【回溯算法】【打卡第187道】：leetCode :93. 复原 IP 地址的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
