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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        dfs(s,res,0,0);
        return res;
    }

    // 记录IP字符串
    private String nums = "";

    // 递归寻找，step表示ip的第几个点，index表示字符串下标索引
    public void dfs(String s,ArrayList<String> res,int step,int index){
        // 当前分割出的字符串
        String cur = "";
        if(step == 4){
            if(index != s.length()){
                return;
            }
            res.add(nums);
        }else{
            // 最长遍历3位
            for(int i = index;i < index + 3 && i < s.length();i++){
                cur += s.charAt(i);
                // 转数字比较
                int num = Integer.parseInt(cur);
                String temp = nums;
                // 不能超过255且不能有前导0
                if(num <= 255 && (cur.length() == 1 || cur.charAt(0) != '0')){
                    // 添加点
                    if(step < 3){
                        nums += cur + ".";
                    }else{
                        nums += cur;
                    }
                    // 递归查找下一个数字
                    dfs(s,res,step + 1,i + 1);
                    // 回溯
                    nums = temp;
                }
            }
        }
    }
}