有效 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 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s仅由数字组成
思路：
本题仍然是字符串切割问题，可以利用回溯解决。用 List<String> result 来接收每一个符合要求的 ip 字符串。在递归回溯时要注意以下几点：
- 无返回值。传入参数为 StringBuilder sb（为了提高字符串操作的效率），int startIndex（指明了应该从字符串的哪个位置开始判断），int dotCount（用来记录已经往字符串里面添加的逗点的数量）。
- 终止条件是：当 dotCount == 3 时终止，这时 字符串被分为四部分，且前三部分是合法的，检验第四部分是否合法，若合法，则将 sb 转为 String 添加进 result 中，返回。
- 单层处理逻辑是：对于[ startIndex,i ] （startIndex<=i<=sb.length()-1）中的子字符串判断其是否合法，若不合法，则从 startIndex 到 i 之后的 子字符串肯定也不合法，故可以直接退出循环。若合法，则给 sb 的第 i+1 个位置添加 逗点 '.'，再进行下一层递归遍历 backTracking()，注意此时传入的 sb 是添加了逗点（在 sb 的 i+1处）之后的 sb，因此下一层递归开始的 startIndex 为 i+2 （前面已经添加了逗点的部分不能再判断），dotCount 要加一。待退出 backTracking 后再进行回溯，删掉 sb i+1 处的逗点。
代码：
class Solution {
List<String> result = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
backTracking(sb,0,0);
return result;
}
public void backTracking(StringBuilder sb,int startIndex,int dotCount){
if(dotCount==3){
if(isValid(sb,startIndex,sb.length()-1)){//判断第四部分是否有效
result.add(sb.toString());
return;
}
}
for(int i=startIndex;i<sb.length();i++){
if(isValid(sb,startIndex,i)){
//如果[startIndex,i]是有效的，那么在 i+1 处添加一个逗点
sb.insert(i+1,".");
//添加一个逗点后,从i+2处开始继续判断剩余部分,逗点数量加1
backTracking(sb,i+2,dotCount+1);
sb.deleteCharAt(i+1);//回溯删除逗点
}
else{
break;//一旦[startIndex,i]之间是无效的,
//那么从 startIndex 到 i之后的字符串就都不是有效的字符串,所以可以退出循环
}
}
}
public boolean isValid(StringBuilder sb,int start,int end){
if(start>end)
return false;
if(sb.charAt(start)=='0'&&start!=end)//首位为0不合法
return false;
int num=0;
for(int i=start;i<=end;i++){
int x = sb.charAt(i)-'0';
num = num *10 + x;
if(num>255)
return false;
}
return true;
}
}参考：代码随想录
