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

题解

题解可参考liweiwei1419和代码随想录

一、判断IP是否合规（注意：这块需要每分割一个数就判断，这样有一个数不满足就递归终止，相当于剪枝）：

• 首先，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址

• 根据截取出来的字符串判断是否是合理的 ip 段，这里写法比较多，可以先截取，再转换成 int ，再判断：
  在0到255之间
  0开头的话只能是0.0.0.0(s.charAt(0)==‘0’&&s.length()!=1,return false)
  数目不等于四组，即num == 4（用num判断，而不需要用string.split()函数分割结果字符串）

二、利用回溯法找分割位置

• 终止条件：startIndex>=s.length()(分割位置越过数组长度，说明已经得到了一个满足条件的IP),path.add(temp)，这里要判断num==4,由于 ip 段就 4 个段，不满足不可以加入结果集
• 每层：限制i<=startIndex+2（剪枝，每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支）和 i<s.length()
  （1）获得本次分割的数组：temp+s.substring(startIndex,i+1))+“.”,注意这里最后一个数字要特殊处理
  （2）判断是否有效，有效则继续进行分割，即进入下一层递归
  （3）分割数字的数目+1，即num++
  （4）回溯：num–
• 递归参数有：
  num：已经分割出多少个 ip 段；
  startIndex：截取 ip 段的起始位置；
  path：记录从根结点到叶子结点的一个路径
  temp:记录当前已经拼接得到的字符串

class Solution {public List<String> path = new ArrayList<>();//用于记录分割了几个整数，已经分割了四次才可能是有效IPpublic int num=0;public List<String> restoreIpAddresses(String s) {//剪枝if (s.length() < 4 || s.length() > 12) return path; dfs(s,"",0);return path;}private void dfs(String s,String temp,int startIndex){//终止if(startIndex>=s.length()){//判断是否有效IPif(num==4) path.add(temp);return;}for(int i=startIndex;i<startIndex+3&&i<s.length();i++){//substring(startIndex,i+1)的取值范围是[startIndex,i]String str=s.substring(startIndex,i+1);if(isValidIP(str)){//分割数字+1num++;//最后一个IP不需要加"."if(num==4) dfs(s,temp+str,i+1);else dfs(s,temp+str+".",i+1);//回溯，但temp+str+"."不需要回溯num--;}else{//这条递归提前终止break;}}}private boolean isValidIP(String s){//以0开头但长度不为1，如023if(s.charAt(0)=='0'&&s.length()!=1) return false;//大小不在0-255之间int temp=Integer.valueOf(s);if(temp<0||temp>255) return false;return true;}
}