Backtracking_93. 复原IP地址

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

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses

---

思路：

 此处要建立一个StringBuilder类型的参数tempAddress，为了对字符串进行处理，存储当前形成的IP地址

IP地址是用三点四段的形式，用count来表示有几段

每加入一个段就count+1，表示多了一个部分，如果不是s的第一个数字就需要在该段的前面加上点

每一部分都需要有最多三个数字组成，用for循环控制，判断是否小于等于255，如果是就递归

最后count到4了就说明已经有四段，需要判断当前形成的四段的IP地址是否是符合要求的，如果符合就加入到动态数组中，不符合就回溯

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> addresses = new ArrayList<>();
        //定义一个StringBuilder类型的变量tempAddress用于存储当前形成的IP地址
        StringBuilder tempAddress = new StringBuilder();
        doRestore(0, tempAddress, addresses, s);
        return addresses;
    }

    private void doRestore(int k, StringBuilder tempAddress, List<String> addresses, String s) {
        //如果已经是四段，或者已经到最后了
        if (k == 4 || s.length() == 0) {
            //如果已经四段，并且还到达了最后
            if (k == 4 && s.length() == 0) {
                //符合条件，加入动态数组
                addresses.add(tempAddress.toString());
            }
            //回溯
            return;
        }
        //每个数字至少有三位，并且不能超过最大长度
        for (int i = 0; i < s.length() && i <= 2; i++) {
            if (i != 0 && s.charAt(0) == '0') {
                break;
            }
            //分离出前i + 1位
            String part = s.substring(0, i + 1);
            if (Integer.parseInt(part) <= 255) {
                if (tempAddress.length() != 0) {
                    //如果数值小于256 并且不是第一位IP地址的第一段就加个点
                    part = "." + part;
                }
                //存放
                tempAddress.append(part);
                //递归
                doRestore(k + 1, tempAddress, addresses, s.substring(i + 1));
                //第一参数开始，将一直到第二个参数的前一个位置的内容都删掉，就是将存放的IP地址不符合的删了重新回溯
                tempAddress.delete(tempAddress.length() - part.length(), tempAddress.length());
            }
        }
    }
}