有效 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 中的任何数字。你可以按 任何 顺序返回答案。
题解
题解可参考liweiwei1419和代码随想录
一、判断IP是否合规（注意：这块需要每分割一个数就判断，这样有一个数不满足就递归终止，相当于剪枝）：
-
首先，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址
-
根据截取出来的字符串判断是否是合理的 ip 段，这里写法比较多，可以先截取，再转换成 int ，再判断：
在0到255之间
0开头的话只能是0.0.0.0(s.charAt(0)==‘0’&&s.length()!=1,return false)
数目不等于四组，即num == 4（用num判断，而不需要用string.split()函数分割结果字符串）
二、利用回溯法找分割位置
- 终止条件：startIndex>=s.length()(分割位置越过数组长度，说明已经得到了一个满足条件的IP),path.add(temp)，这里要判断num==4,由于 ip 段就 4 个段，不满足不可以加入结果集
- 每层：限制i<=startIndex+2（剪枝，每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支）和 i<s.length()
（1）获得本次分割的数组：temp+s.substring(startIndex,i+1))+“.”,注意这里最后一个数字要特殊处理
（2）判断是否有效，有效则继续进行分割，即进入下一层递归
（3）分割数字的数目+1，即num++
（4）回溯：num– - 递归参数有：
num：已经分割出多少个 ip 段；
startIndex：截取 ip 段的起始位置；
path：记录从根结点到叶子结点的一个路径
temp:记录当前已经拼接得到的字符串
class Solution {
public List<String> path = new ArrayList<>();
//用于记录分割了几个整数，已经分割了四次才可能是有效IP
public int num=0;
public List<String> restoreIpAddresses(String s) {
//剪枝
if (s.length() < 4 || s.length() > 12) return path;
dfs(s,"",0);
return path;
}
private void dfs(String s,String temp,int startIndex){
//终止
if(startIndex>=s.length()){
//判断是否有效IP
if(num==4) path.add(temp);
return;
}
for(int i=startIndex;i<startIndex+3&&i<s.length();i++){
//substring(startIndex,i+1)的取值范围是[startIndex,i]
String str=s.substring(startIndex,i+1);
if(isValidIP(str)){
//分割数字+1
num++;
//最后一个IP不需要加"."
if(num==4) dfs(s,temp+str,i+1);
else dfs(s,temp+str+".",i+1);
//回溯，但temp+str+"."不需要回溯
num--;
}else{
//这条递归提前终止
break;
}
}
}
private boolean isValidIP(String s){
//以0开头但长度不为1，如023
if(s.charAt(0)=='0'&&s.length()!=1) return false;
//大小不在0-255之间
int temp=Integer.valueOf(s);
if(temp<0||temp>255) return false;
return true;
}
}
