给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
ip地址由三个小数点（.）分割成四段，每一段取值为0~255。所以输入字符串s最长为12，最少为4位。
以2556....来划分的话，第一段有可能是下面三种情况：
所以采用递归框架，从某一位置开始，往后依次截取3、2、1，但是如果某一段截取到的情况是下面两种则不用继续深入：
即剪枝条件：不能以0开头，不能大于255.
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if(s.length()>12||s.length()<4)
return result;
digui(result,s,0,0);
return result;
}
public void digui(List<String> list,String tmp,int pos,int count){
//结束条件
if(count==3){
if(pos+3>tmp.length()-1&&isValid(tmp.substring(tmp.lastIndexOf(".")+1)))
list.add(tmp);
}
//业务处理
if(pos+3<tmp.length()&&isValid(tmp.substring(pos,pos+3))){
String thirdTmp = tmp.substring(0,pos+3)+"."+tmp.substring(pos+3);
digui(list,thirdTmp,pos+4,count+1);
}
if(pos+2<tmp.length()&&isValid(tmp.substring(pos,pos+2))){
String secondTmp = tmp.substring(0,pos+2)+"."+tmp.substring(pos+2);
digui(list,secondTmp,pos+3,count+1);
}
if(pos+1<tmp.length()){
String firstTmp = tmp.substring(0,pos+1)+"."+tmp.substring(pos+1);
digui(list,firstTmp,pos+2,count+1);
}
}
public boolean isValid(String s){
int val = Integer.valueOf(s);
if(val>255)
return false;
//用于处理0XX或0X的情况
if(!String.valueOf(val).equals(s))
return false;
return true;
}
}
暴力通常可以解决问题，但是肯定不是最高效的方法，这里对字符串的处理占用了太多内存和时间。有没有更好的办法呢？
待续...
原文：https://www.cnblogs.com/MrSaver/p/11610149.html