public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res=new ArrayList<>();
        dfs(s,res,0,"",0);
        return res;
    }
    private void dfs(String ip,List<String> res,int start,String s,int count){
        if(count>4) return;
        if(count==4&&start==ip.length()){
            res.add(s);
            return;
        }
        for(int i=1;i<4;i++){
            if(start+i>ip.length()) break;
            String temp=ip.substring(start,start+i);
            if((temp.startsWith("0")&&temp.length()>1)||(i==3&&Integer.parseInt(temp)>=256)) continue;
            dfs(ip,res,start+i,s+temp+(count==3?"":"."),count+1);
        }
    }
}