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 中的任何数字。你可以按 任何 顺序返回答案。

分析：本题难度较大，与上一道分割回文子串有些类似，同样需要一个辅助函数来判断字符子串是否是ip地址，而本题多了次数的限制，即不多不少，必须分成4个，那么在传递参数的时候要将当前切割次数传递过去
还有一个特别的点，由于一次添加的不是一个字符，而是一个字符串，用StringBuilder来记录path，并使用deleteCharAt(path.length-1)来回溯就不好使了，本题为了可以继续记录回溯过程，直接在字符串s上进行变动，这也是没有办法的办法

参考代码：
public List restoreIpAddresses(String s) {
sup(s,0,0);
return ret;
}
List ret = new ArrayList<>();
//cut为分割次数，只能分割3次，不多不少，所以在分割3次后，就要判断是否可以加入结果集，并结束最终的递归
private void sup(String s,int index,int cut){
if(cut==3){
if(isvalid(s,index,s.length()-1)){
ret.add(s);
}
return;
}
for(int i=index;i if(!isvalid(s,index,i)) break;
cut++;
//在字符串s上使用子串拼接的方式来记录回溯过程
s=s.substring(0,i+1)+”.”+s.substring(i+1);
sup(s,i+2,cut);
cut—;
s=s.substring(0,i+1)+s.substring(i+2);
}
}
//判断字符子串是否为有效IP地址
private boolean isvalid(String s,int start,int end){
if(start>end) return false;
if(s.charAt(start)==’0’&&start!=end) return false;
int num=0;
for(int i=start;i<=end;i++){
if(s.charAt(i)<’0’||s.charAt(i)>’9’) return false;
num=num*10+(s.charAt(i)-‘0’);
if(num>255) return false;
}
return true;
}