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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
 

class Solution {List<String> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<String> restoreIpAddresses(String s) {//这里就是对字符串的预处理，但是对于测试用例来说我觉得用处不大，毕竟不会蠢到用13位数字让你分割if(s.length()<4 || s.length()>12){return res;}//这里就是套用最经典的回溯模板了，相比于分割字符串只加入分割线一个参数以外，这里还需要添加额外的层数参数level//因为合法的IP地址只有四段，我们不能无限对其进行分割backtracking(s,0,0);return res;}// 判断分割出来的每一段字符串是否是合法的IP地址boolean isValidIp(String s){//判断其是否含有前导0if(s.charAt(0)=='0' && s.length()>1){return false;}//长度为4就直接舍弃，加上这一步是为了后面parseInt做准备,防止超过了Integer可以表示的整数范围if(s.length()>3){return false;}//将字符转为int判断是否大于255，因为题目明确说了只由数字组成，所以这里没有对非数字的字符进行判断if(Integer.parseInt(s)>255){return false;}return true;}void backtracking(String s,int splitIndex,int level){//递归终止条件，分割的四个字符串都是合法的IP地址if(level==4){//在代码的最后再利用join函数加上“.”,构造IP地址的表示形式res.add(String.join(".",path));return;}for(int i=splitIndex;i<s.length();i++){//每一次分割之后，对剩余字符长度是否合理进行判断，剪枝操作，优化运行速度if((s.length()-i-1) > 3*(3-level)){continue;}//如果分割的字符串不是合理的IP地址，跳过if(! isValidIp(s.substring(splitIndex,i+1))){continue;}//把合法的IP地址段加入path存储path.add(s.substring(splitIndex,i+1));//每次把分割线往后移一位，且段数level+1backtracking(s,i+1,level+1);//进行回溯操作path.remove(path.size()-1);}}
}