LeetCode_85_RestoreIPAddresses

发布日期: 2022-06-07

更新日期: 2022-06-07

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

1. question: 复原IP地址（中等）

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

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

示例 1：

1 2	输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]

示例 2：

1 2	输入：s = "0000" 输出：["0.0.0.0"]

示例 3：

1 2	输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

1 2	1 <= s.length <= 20 s 仅由数字组成

2. answers

这道题和分割回文串类似。只不过这道题限制了将字符串分割成4个子串。并且限制了每个子串的数值大小。主要有如下要求：

每个数字不能大于255，即限制了每个数字的长度最多为3位，即每个数字最多有三个选择。
每个数字不能以0开头。
4个数字必须将字符串完全用完。

所以，递归的终止条件是生成了4个数字，且字符串遍历完。代码如下所示：

public class Solution_0084 {

    // 保存最终结果
    public List<String> result = new ArrayList<>();

//    // 保存生成的IP地址
//    StringBuilder sb = new StringBuilder();   // 注意，此处不能使用成员变量，因为这样做会使得不同数字之间覆盖，

    // 保存生成的IP地址（4位数字）
    public LinkedList<String> ip = new LinkedList<>();

    public void generateIP(char[] chars, int startIndex) {

        // 注意，递归终止条件
        // 生成四位数字。
        if(ip.size() == 4) {

            // 如果没有遍历完完数组，就不将结果加入。
            if(startIndex == chars.length) {

                // 拼接IP
                StringBuilder sbs = new StringBuilder();
                for(String str: ip) {
                    sbs.append(str).append(".");
                }

                sbs.deleteCharAt(sbs.length() - 1);
                result.add(sbs.toString());
            }

            return;
        }


        // 每个数有如下选择，注意，一个数字最多有三种选择。即限制了最多三位数
        int endIndex = Math.min(startIndex + 2, chars.length - 1);
        // 保存本数字
        StringBuilder sb = new StringBuilder();
        for (int i = startIndex; i <= endIndex; i++) {

            // 生成本数
            // 判断本数是否满足要求，如不满足，继续生成

            // 1. 形成新数字，并判断是否满足要求
            sb.append(chars[i]);

            // 2. 判断是否是0开头，如果是还没生成数字，但是第一个字符却是0，显然，是上一个数字切割不合理。
            // 但是要注意，如果只有一个数字，并且是0，是可以的。
            if(sb.length() > 1 && sb.charAt(0) == '0') return;

            // 3 因为如果当前数字已经大于255了，说明本选择已经没办法再满足了，因为最多是三位数，并且下次只能是4位数了。
            // 但是因为外层for循环已经限制了三位数，所以这里continue和return的效果是一样的。
            if(Integer.parseInt(sb.toString()) > 255) return;

            // 此时生成了满足要求的数字
            ip.add(sb.toString());

            // 3. 此时数字一定满足要求。递归下一位数字
            generateIP(chars, i + 1);

            // 回溯，删除最后形成的数字
            ip.removeLast();
            // 此处无需将sb清空，因为如果1满足了，后续12可能还满足。只有当sb中的数字大于255了，才开始清空。

        }

    }

    public List<String> restoreIpAddresses(String s) {

        if(s.length() >= 4)
            generateIP(s.toCharArray(), 0);

        return result;
    }

    public static void main(String[] args) {

//        String str = "25525511135";
//        String str = "0000";
//        String str = "101023";
        String str = "1";

        Solution_0084 s = new Solution_0084();

        List<String> strings = s.restoreIpAddresses(str);

        for(String strs: strings){
            System.out.println(strs);
        }

    }
}