复原IP地址

QUESTION:

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: “25525511135” 输出: [“255.255.11.135”, “255.255.111.35”]

EXPLANATION:

说实话，我觉得leetcode中国上的这些破题目挺蠢的。自己不说限定条件，只把题目一摆，虽然有些testcase是肯定会想到的，但是还有一些就很烦。好了，不吐槽这个了，这道题目是典型的回溯算法，回溯算法的公式其实百度上也有就是如果条件满足添加到结果中，否则就继续进行迭代。
只要把这个思路套在公式里就可以。
立即如下：
1.首先从第一位开始，因为每个ip地址的分段只能包含最多3个数
2.然后将结果和当前的index传给下次循环
3.在循环到第三次的时候，可以看一下剩下的字符是否满足，如果满足则说明可以添加到结果中
这样就将每个分段都进行了1-3次的遍历，这样就可以得到对应的结果。

SOLUTION:

class Solution {
    public List<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<>();
        if(s.length()>12) return result;
        restoreIpAddressesHelper(result,0,0,"",s);
        return result;
    }
    
    public static void restoreIpAddressesHelper(ArrayList result,int start,int count,String tmp ,String s){
        if(count == 3 && restoreIpAddressesUtils(s.substring(start,s.length()))){
            result.add(tmp+s.substring(start,s.length()));
        }else{
            if(count<=2){
                for(int i = 1;i<=3;i++){
                    if(start+i<s.length()){
                        String i_tmp = s.substring(start,start+i);
                        if(restoreIpAddressesUtils(i_tmp)){
                            i_tmp = tmp+i_tmp+".";
                            restoreIpAddressesHelper(result,start+i,count+1,i_tmp,s);
                        }
                    }
                }
            }
        }
    }

    public static boolean restoreIpAddressesUtils(String s){
        if(s.isEmpty()) return false;
        if(s.length()>1 && s.startsWith("0")) return false;
        int num = Integer.parseInt(s);
        return num>=0 && num<=255;
    }
}
>
--> return <--