题目描述：
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
题解：
class Solution {
public List<String> restoreIpAddresses(String s) {
}
}
题解：
还是使用回溯法
public class L93 {
public static List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if(s.length()<4){return Collections.EMPTY_LIST;}
Stack<String> temp = new Stack<>();
getIpAddresses(s,0,0,temp,result);
return result;
}
public static boolean valid(String ss){
if(Integer.valueOf(ss) <= 255 && Integer.valueOf(ss)>0 && !ss.startsWith("0")){
return true;
} else if(ss == "0" || ss.equals("0")){
return true;
}
return false;
}
public static void getIpAddresses(String ss, int j, int i, Stack<String> temp, List<String> result){
if(i == 4 && j == ss.length()){
String xx = "";
for(int index =0;index<temp.size()-1;index++){
xx += temp.get(index) + ".";
}
xx += temp.get(temp.size()-1);
result.add(xx);
return;
}else if(i == 4 && j < ss.length()){
return;
}
for(int index =1;index<=3;index++){
//判断当前选取的字符串是有效的
if(j+index<=ss.length() && valid(ss.substring(j,j+index))){
i ++;
//那么就需要将此数保存,保存之前需要判断是不是入值得是第四个，如果是第四个，那么ss应该到头
temp.push(ss.substring(j,j+index));
//继续进行向下一个遍历
getIpAddresses(ss,j+index,i,temp,result);
//将数从栈中弹出
temp.pop();
i--;
}else{
//如果当前选取的无效，那么久继续遍历
return;
}
}
}
public static void main(String[] args) {
restoreIpAddresses("255");
}
}
