题解 | #数字字符串转化成IP地址#

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */

     ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        int n = s.length();

        dfs(s,0,0); 
        return res;
    }


   //用来记录这次回溯从第0步开始 到第4步结束所生成的字符串
    private String nums = "";

    //begin 为当前字符 depth是当前步骤数
    void dfs(String s , int begin , int depth){
        //当前步骤的一个字符串
        String cur = "";

        //回溯结束时
        if(depth == 4){
            //0~3步已经处理完字符串了 第4步应该在最末尾
            if(s.length() != begin ) return ;

            res.add(nums);
        }else{
            //当depth = 0 ~ 3时为补充nums的过程

            String temp = nums; //先记录变量 方便回溯

            //由于点与点之间最多3个字符 遍历cur分别为1个字符 2个字符 3个字符的情况
            for(int i = begin ; i < begin + 3 && i < s.length(); i++){
                //将当前 字符加到cur
                  cur+=s.charAt(i);
               int number =  Integer.parseInt(cur);

               //如果数字非法 或者出现前导0  就是一个数字开头是0的情况 
               if(number > 255  || (cur.length() > 1 && cur.charAt(0) == '0')){
                      continue;
               }

                nums += cur;
               if(depth < 3){
                nums+=".";
               }

               //开始递归
               dfs(s,i+1,depth+1);
                //递归结束  开始回溯
                nums = temp;


            }

        }
    }
}