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

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        //递归
        ArrayList<String> res = new ArrayList<>() ;
        if(s == null || s.length() < 4) return res ;
        recur(s , 0 , 4 , "" , res) ;
        return res ;
    }
    //思想：处理从index开始的后续字符串如何转换为fra段【如recur(str,0,4,tmp,res)】,处理从str[0]开始的后续字符串
    //如何转换为符合要求的4段。每次选择当前的一个从index开始的前导字符串组成当前段，然后把问题转换为剩下的字符串组成剩下
    //的段
    //1.tmp：当前已经拼接好的段
    //2.res:保存结果
    public void recur(String str , int index , int fra , String tmp , ArrayList<String> res) {
        if(fra == 0 && index == str.length()) {//IP地址的所有段都拼接完，而且字符串也刚好用完
            res.add(tmp) ;
            return ;
        }
        //拼接的不合适
        if(fra == 0 && index != str.length() || fra != 0 && index == str.length()) {
            return ;
        }
        //检测从index往后的几个字符组成的数字满不满足要求[0-255]
        int i = index + 1 ;
        int j = 0 ;//最多也只能由三个字符组成
        for(; i <= str.length() && j < 3 ; i ++ , j ++) {
            String cur_str = str.substring(index , i) ;//当前段选择的字符串
            if(isOK(cur_str)) {
                if("".equals(tmp)) {//第一段前面，不拼接‘.’
                    recur(str , i , fra-1 , tmp+cur_str , res) ; //递归，处理从i开始的后续字符串如何转换为fra-1段   
                } else {
                    recur(str , i , fra-1 , tmp+"."+cur_str , res) ;
                }
                
            } 
        }
    }
    //检测字符串是否满足[0-255],且不含前导0
    public boolean isOK(String str) {
        //有前导0的数字也不合法
        if(str.length() >= 2 && str.charAt(0)=='0') return false ;
        int num = Integer.parseInt(str) ;
        return num >= 0 && num <= 255 ;
    }
}