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

回溯加剪枝，需要5个参数。

代码：

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    ArrayList<String> res;
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        res=new ArrayList<>();
        if(s.length()<4){
            return res;
        }
        dfs(s,0,4,s.length(),new StringBuilder());
        return res;
    }
  //参数含义：原字符串s；当前递归层开始的索引index；一共有4个部分，当前还剩remainderBlock个部分需要填充；s的长度len，可能的结果stb
    private boolean dfs(String s,int index,int remainderBlock,int len,StringBuilder stb){
        if(remainderBlock==0&&index==len){
            stb.deleteCharAt(stb.length()-1);
            res.add(new String(stb));
            return true;
        }
        if((len-index)>(remainderBlock*3)||len==index){//剩余元素过多或者不够分，都要提前结束
            return false;
        }
        int n=Math.min(len,index+3);
        for(int i=index+1;i<=n;i++){
            String temp=s.substring(index,i);
            if(Integer.parseInt(temp)>=0&&Integer.parseInt(temp)<256){
                if(i-index>1&&temp.startsWith("0")){
                    continue;
                }
                stb.append(temp);
                stb.append(".");
                if(dfs(s,i,remainderBlock-1,len,stb)){
                    stb.delete(stb.length()-(i-index),stb.length());
                }else{
                    stb.delete(stb.length()-(i-index)-1,stb.length());
                }
            }
        }
        return false;
    }
}