[数据结构与算法]多看看把，条件太多了--leetcode 93. 复原 IP 地址

难度：中等
频次：62

题目：

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

解题思路：DFS递归法+回溯<剪枝条件有点多>

注意：

• 递归结束条件：temp数量为4了，并且start == s.length
• 剪枝条件
  • temp数量为4了，但是start还没结束s的遍历
  • for循环里每次切分所得到的完整字符串不能越s的边界
  • for循环里 从start的位置切分时，如果切分的数量为2、3，那么第一位不能是0
  • for循环里 从start的位置切分时，如果切分数量位3时，3位数大小不能大于255
• 最后得到的temp数组要转换成IP【StringBuilder】的格式（带.的长字符串）,然后再添加到res里------这里有一个函数没怎么用 IP.deleteCharAt（n）
• string转换成int Integer.parseInt(s);
• 最后需要回溯，所以需要移除数组尾部刚添加的元素

代码

class Solution {
    //放的是最后修改过后的结果
    List<String> res=new ArrayList<>(); 
    //放的是修改结果格式之前的数字数组，没有.
    List<String> temp=new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        DFS(s,0);
        return res;
    }
    public void DFS(String s,int start)
    {   
        //递归结束条件：start==s.length()-1 则说明经过上面的递归后，s还剩1位可以分配
        if(temp.size()==4&&start==s.length()){
            StringBuilder IP=new StringBuilder();
            for(String a:temp){
                IP.append(a).append(".");
            }
            //这个函数一般时候还真记不住
            IP.deleteCharAt(IP.length()-1);
            res.add(IP.toString());
            return;
        }
        //剪枝条件：1.如果temp.size==4&&start<s.length()
        if(temp.size()==4&&start<s.length()) return ;
        //切分 i=3是因为 每个ip的位置不能超过255   比如 123 start指向1 切分方式：1    12   123
        //最多四层
        for(int step=1;step<=3;step++){
            //切分的时候不能越界
            if(start+step-1>=s.length()) return;
            //2位和三位的时候--第一位不能是 01 022
            if(s.charAt(start)=='0'&&step!=1) return ;
            String smalltemp=s.substring(start,start+step);
            //如果裁剪出来的子字符串的数字比255大
            if(step==3&&Integer.parseInt(smalltemp)>255) return;
            temp.add(smalltemp);
            DFS(s,start+step);
            temp.remove(temp.size()-1);
        }
    }
}