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

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // 向 s 中 插入 3 个点 且每个点 相距 dis 属于 [1,3] ;
        // 通过深度优先 回溯的方式去更新点可以存在的位置 
        // 在一个判定中去判定 最终得到的结果是否符合要求 
        ArrayList<String> ans = new ArrayList<>();
        if(s.length() > 12) return ans;
        dfs(ans,new StringBuilder(),0,s,0);
        return ans;
    }
      // cut_index 代表上一个切点的下标!
     private void dfs(List<String> ans,StringBuilder child,int cut_index,String s,int count){
        if(count == 3){
            // 第一次到达 count == 3
            // 说明 后面的东西 还没 加入到 child 所以还要操作一波 
            child.append(s.substring(cut_index,s.length()));
            if(isLegal(child.toString())){
                ans.add(new String(child.toString()));
            }
            child.delete(child.length() - (s.length() - cut_index) ,child.length()); 
            return ;
        }

        for(int i = 1; i <= 3 && cut_index + i < s.length(); i++){
            child.append(s.substring(cut_index,cut_index + i));
            child.append('.');
            dfs(ans,child,cut_index + i,s,count + 1);
            child.delete(child.length() - i - 1,child.length());// 回溯 
        }

    }

    private boolean isLegal(String address){
        String[] digits = address.split("\\."); // 通过 . 把字符串 拆成四块 (讲道理第一次被转义字符秀了一手) 
        if(digits.length < 4){
            return false;
        }else{
            for(String dress : digits){
                if(Long.parseLong(dress) > 255 || (dress.length() > 1 && dress.charAt(0) == '0')) return false; // 这里用 Long 主要是因为 java 没有 unsign int 
            }
        }
        return true;
    }
}