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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */

    // 通过回溯的方法解决
    // 1. 使用list记录路径，当遍历到末尾的时候，计算该列表的内容
    // 2. checkIp的结果
    // 3. 回溯+减枝
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> list = new ArrayList<>();
        List<String> dequeue = new ArrayList<>();
        dfs(list,0,dequeue,s);
        return list;
    }

    private void dfs(ArrayList<String> list,int start,List<String> dequeue,String s){
        // 出口
        if(start == s.length() && dequeue.size() ==4){
            list.add(getStringByList(dequeue));
            return;
        }

        if(dequeue.size() >4){
            return;
        }

        for(int l = start+1;l<=s.length();l++){
            String ipStr = s.substring(start,l);
            if(isValidIpString(ipStr)){
                dequeue.add(ipStr);
                dfs(list,l,dequeue,s);
                dequeue.remove(dequeue.size()-1);
            }else{
                return;
            }
        }

    }

    private boolean isValidIpString(String ipStr){
        if(ipStr.charAt(0)=='0' && ipStr.length() >1){
            return false;
        }
        int ip = Integer.valueOf(ipStr);
        return ip >=0 && ip <=255;
    }

    private String getStringByList(List<String> dequeue){
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<dequeue.size();i++){
            if(i==0){
                sb.append(dequeue.get(i));
            }else{
                sb.append(".").append(dequeue.get(i));
            }
        }
        return sb.toString();
    }

}