93. 复原 IP 地址

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：递归+回溯

IP地址一共有四个整数组成，每次递归找出一个有效的整数，当选择4个整数，并且字符串s也已经达到末尾，即找到一个有效的IP地址。

1. 全局变量：
   1. List result：用于保存所有的有效IP地址
   2. List tem：用于保存每一部分的整数
2. 函数定义：process(String s, int index)，从s[index]位置开始寻找一个有效的整数
   1. 递归终止条件：
      1. 如果index>=s.length() && tem.size()==4：则已经找到4个有效的整数，将tem里的字符串拼接程有效的IP地址，return
      2. 如果index>=s || tem.size()==4：即字符串s已经使用完，但是还没有找到4个有效的数字，或者s没有使用完，但是已经找到了4个有效的数字，此时，都直接return
   2. 每个有效数字可以是0-255之间的数字，所以选择截取1个，2个或者3个字符，判断截取的字符是否是一个有效的整数，所以使用循环进行截取这三种情况：
      1. 如果s[index] == '0'，则只能截取1个字符：
         1. tem.add("0")
         2. process(s, index+1)
         3. tem.remove(tem.size()-1)：回溯
         4. break：直接跳出循环，因为当前字符为0，只能截取1个字符
      2. 否则：如果截取的字符组成的数组小于等于255，则其是一个有效的整数：
         1. tem.add(part)：part是截取的字符
         2. process(s, index+1)
         3. tem.remove(tem.size()-1)：回溯

如果s的长度小于4或者大于12，一定不能组合成一个有效的IP，直接返回空列表

AC代码：

class Solution {
    public List result;
    public List tem;
    public List restoreIpAddresses(String s) {
        result = new ArrayList<>();
        tem = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) {
            return result;
        }
        process(s, 0);
        return result;
    }
 
    public void process(String s, int index) {
        if (index >= s.length() && tem.size() == 4) {
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < tem.size(); i++) {
                if (i==0){
                    ans.append(tem.get(i));
                }else {
                    ans.append(".").append(tem.get(i));
                }
            }
            result.add(ans.toString());
            return;
        } else if (index >= s.length()||tem.size()==4) {
            return;
        }
 
        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length()) {
                break;
            }
            String part = s.substring(index, index + i);
            if (s.charAt(index) == '0') {
                tem.add("0");
                process(s, index + 1);
                tem.remove(tem.size() - 1);
                break;
            } else if (part.length() <= 2 || part.compareTo("255") <= 0) {
                tem.add(part);
                process(s, index + i);
                tem.remove(tem.size() - 1);
            }
        }
    }
}