93. 复原IP地址

本题来自LeetCode：93. 复原IP地址^[1]

题目描述

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

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

题目分析

IP地址可能为成四段，每段的数值范围为 [0, 255]。并且没有前缀 0（即没有 011等数值）。
本题可以采用深度遍历，每次生成一段，这段可能包含 1位数、 2位数、 3位数，校验这些数值是否位于区间 [0, 255]。

题目解答

class Solution {
    private ListString ips = new ArrayList();
    public ListString restoreIpAddresses(String s) {
        restoreIpAddress("", 0, s, 0);
        return ips;
    }

    public void restoreIpAddress(String ip, int rangeCount, String s, int start) {
        if(start == s.length()) {
            if(rangeCount == 4) {
                ips.add(ip);
            }
            return;
        }
        if(rangeCount == 4) {
            return;
        }

        int number = 0;
        // 校验接下来1位、2位、3位数字组合是否位于区间[0...255]
        for(int i = start; i  s.length() & i  start + 3; i ++) {
            int digit = s.charAt(i) - '0';
            number = number * 10 + digit;
            // 当前段合法，继续校验
            if(number = 0 && number = 255) {
                restoreIpAddress(ip + (rangeCount == 0 ? "" : ".") + number, rangeCount + 1, s, i + 1);
            }
            // 表示当前段只能是'0'
            if(number == 0) {
                break;
            }
        }
    }
}

复杂度分析：
时间复杂度： O(3^4)
空间复杂度： O(1)

参考资料

93. 复原IP地址: https://leetcode-cn.com/problems/restore-ip-addresses

原文始发于微信公众号（xiaogan的技术博客）：