面接：文字列：IPアドレス抽出

テーマ
数字だけの文字列を指定して、すべての適法なipアドレスを返します。
アルゴリズム

ipアドレスは4段

です。

各段の3つの場合：（1）一つの数字だけを取って（2）二つの数字を取って、最初の数字は0（3）ではなく3つの数字を取って、最初の数字は0ではなく、3つの数字からなる数は256/再帰

より小さいです。

import java.util.*;


class Solution{
    public ArrayList<String> restoreIpAddress(String s){
        ArrayList<String> res=new ArrayList<String>();
        String ip="";
        restoreIpAddress(s,0,0,ip,res);
        return res;
    }

    private void restoreIpAddress(String s,int start,int part,String ip, ArrayList<String> res){
        //   ，   
        if(s.length() -start >(4-part)*3) return;
        //       
        if(s.length()-start <(4-part))  return;
        //       ip
        if(start==s.length() && part ==4) {
            //       
            res.add(ip.substring(0,ip.length()-1));
            return;
        }
        int num =0;
        for(int i=start;i<Math.min(start+3,s.length());i++){
            //         
            num = num*10 +(s.charAt(i)-'0');
            if(num<=255){
                //  ip         256
                ip+=s.charAt(i);
                restoreIpAddress(s,i+1,part+1,ip+'.',res);
            }
            //      0  ，   0，   0x     
            if(num==0)  break;

        }
        }
    }