题目：

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

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

解答：

class Solution {
    
    public List<String> restoreIpAddresses(String s) {
        
        List<String> res = new ArrayList<>();
        
        if(s.length() < 4 || s.length() > 12) return res;
        
        helper(res, s, "", 0);
        
        return res;
    }
    
    public void helper(List<String> res, String s, String cur, int index){
        
        //必须同时满足段数为4，s字符串已经用完，才可以添加到结果中
        if(index == 4 && s.length() == 0) res.add(cur.substring(1));
        
        //上面二者条件如果只满足一条，就直接返回
        else if((index == 4 && s.length() != 0) || (index != 4 && s.length() == 0)) return;
        
        else {
            
            //第一种情况，取s的第一位
            helper(res, s.substring(1), cur + "." + s.substring(0, 1), index + 1);
            
            //第二种情况，取s的前两位，但是s的第一位不能为0
            if(s.charAt(0) != '0' && s.length() > 1){     
                helper(res, s.substring(2), cur + "." + s.substring(0, 2), index + 1);   
            }
               
            //第三种情况，取s的前三位，但是s的第一位不能为0并且前三位转为数字后要小于255
            if(s.charAt(0) != '0' && s.length() > 2 && Integer.valueOf(s.substring(0, 3)) <= 255) {   
                helper(res, s.substring(3), cur + "." + s.substring(0, 3), index + 1);
            }  
        }
    }
}