LeetCode93. 复原 IP 地址

LeetCode93. 复原 IP 地址

题目描述

/**
     * 
     * 给定一个只包含数字的字符串，用以表示一个 IP 地址，
     * 返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
     * <p>
     * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），
     * 整数之间用 ‘.‘ 分隔。
     * <p>
     * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
     * 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
     *
     */

思路分析

1. 复原IP地址，即给定一个数字字符串，按照IP地址规则将其复原为多个满足条件的IP地址
2. 很容易想到递归 + 回溯的方法
3. 定义一个大小为4 的全局数组，用于保存IP地址的每一段，因此还需要一个索引记录是那一段
4. 使用深度优先的方式，即遍历字符串，选择一个满足条件的数字字符串作为IP地址的第一段，等条件不满足或找到满足的后再回溯寻找第一个满足的其他字符串，然后从未选择的字符串开始，依次再选择第二段，第二段仍然有很多选择，先选择一个，等条件不满足或找到满足的后再回溯，直至选择到最后一段
5. 不断的递归 + 回溯，直到找到所有满足的或者筛选掉所有不满足的
6. 递归结束的条件为保存每一段的数组中都存储了满足格式的字符串，并且字符串全部遍历结束，说明找到满足IP递归规则的，则结束
7. 或者数组已满，但是字符串还没有遍历完，说明不满足
8. 还要考虑字符串的某一位为零的情况，则直接将零作为单独的一段即可
9. 其他正常情况递归+回溯即可
10. 源码见下

源码及分析

//表示总共将字符串分为4段
    static final int SEG_COUNT = 4;
    //创建集合保存结果
    List<String> list = new ArrayList<>();
    //创建数组保存每一段的元素
    int[] segments = new int[SEG_COUNT];

    public List<String> restoreIpAddresses(String s) {
        dfs(s,0,0);
        return list;
    }

    /**
     * 从字符串s的start位置开始寻找下一段的元素
     *
     * @param s     字符串
     * @param seg   表示第几段
     * @param start 下一段开始位置索引
     */
    public void dfs(String s, int seg, int start) {
        //如果找到了四段ip并且遍历完了字符串，那么就是一种答案
        if (seg == SEG_COUNT){
            if (start == s.length()){
                //走到这一步说明segments数组中已经存在一个满足要求的答案，将其拼接转成字符串即可
                StringBuffer ipAddress = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; i++) {
                    //拼接字符串
                    ipAddress.append(segments[i]);
                    //拼接 .
                    if (i != SEG_COUNT - 1){
                        ipAddress.append(‘.‘);
                    }
                }
                //将拼接后的结果添加到集合中
                list.add(ipAddress.toString());
            }
            //找到一个后继续回溯
            return;
        }
        //如果还没找到4段IP就已经遍历完了字符串，那么提前回溯
        if (start == s.length()){
            return;
        }
        //由于前导不能为零，如果遇到零，只能将0作为这一段的ip
        if (s.charAt(start) == ‘0‘) {
            segments[seg] = 0;
            dfs(s, seg + 1, start + 1);
        }
        //正常情况下，枚举每一种可能性并递归
        //定义变量保存每一段的结果
        int address = 0;
        //从start开始遍历，直到遍历完字符串
        for (int i = start; i < s.length(); i++) {
            //先将每一段的字符转为数字
            address = address * 10 + (s.charAt(i) - ‘0‘);
            //判断当前段的地址是否满足条件，如果满足，则递归判断下一段，否则结束
            if (address > 0 && address <= 255) {
                segments[seg] = address;
                dfs(s, seg + 1, i + 1);
            }else {
                break;
            }
        }
    }

LeetCode93. 复原 IP 地址

原文：https://www.cnblogs.com/mx-info/p/14898168.html