package leetcode;

import java.util.ArrayList;
import java.util.List;

public class demo_93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> list=new ArrayList<String>();
        //不符合IP地址长度范围
        if(s.length()>12||s.length()<4) {return list;}
        backtrack(s, list, new ArrayList<String>());
        System.out.println(list);
        return list;
    }
    public void backtrack(String s,List<String> list,List<String> alist) {
        //每次取字符串前1-3的子串
        for(int index=1;index<4;index++) {
            //防止最后取子串越界
            try {
                String s2=s.substring(0,index);
                //除0外，不出现以0开头的数
                if(s2.length()!=1&&s2.startsWith("0")) {break;}
                //每个位置的大小0-255
                if(Integer.valueOf(s2)<0||Integer.valueOf(s2)>255) {break;}
                alist.add(s2);
                if(alist.size()<4) {
                    backtrack(s.substring(index), list, alist);
                }
                //如果正好全部都能被分割完
                if(alist.size()==4&&s.substring(index).equals("")) {
                    String ss="";
                    for(String s1:alist) {
                        ss=ss+s1+".";
                    }
                    ss=ss.substring(0,ss.length()-1);
                    //存入到list中
                    list.add(ss);
                }
                //如果被分割后还有剩余子串则继续
                else {
                    alist.remove(alist.size()-1);
                    continue;
                }
                alist.remove(alist.size()-1);
            } catch (Exception e) {
                // TODO: handle exception
                break;
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_93 d93=new demo_93();
        String s="101023";
        d93.restoreIpAddresses(s);
    }

}