题目

有效 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 中的任何数字。你可以按任何顺序返回答案。

示例：

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

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

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

解答 & 代码

递归回溯

class Solution {
private:
    int SEG_COUNT = 4;
    vector<string> resultList;    // 结果数组
    vector<int> segments;        // 存储当前 ip，分为四个整数存储于数组中

    // 将当前的 ip（即数组 segments 的 4 个数）转化为 string 存储到结果数组 resultList 中
    void saveIP()
    {
        string ip = "";
        for(int i = 0; i < SEG_COUNT; ++i)
        {
            ip += to_string(segments[i]);
            if(i != SEG_COUNT - 1)
                ip += ".";
        }
        resultList.push_back(ip);
    }

    // 递归回溯
    // start 是当前遍历到的字符串 s 的下标（即第 segIdx 段的首位数字）
    // segIdx 代表当前处理 ip 中的第几段数字（segIdx in [0, 3]）
    void backTrack(string s, int start, int segIdx)
    {
        // 如果已经处理完了 4 段 ip 地址（当前 segIdx == 4）
        if(segIdx == SEG_COUNT)
        {
            if(start == s.size())    // 且字符串已遍历完
                saveIP();            // 则保存当前的 IP
            return;                    // 直接返回，结束递归
        }

        // 如果还没找完 4 段 ip，但是字符串已遍历完，直接返回，结束递归
        if(start == s.size())
            return;

        // 特殊处理前导 0
        // 如果当前这段 ip 数字的首位是 0，那么这一段只能为 0
        if(s[start] == '0')
        {
            segments[segIdx] = 0;
            backTrack(s, start + 1, segIdx +1);        // 递归回溯
            return;
        }

        // 正常情况
        int num = 0;
        // 当前这段 ip 数字可能有 3 种长度：1、2、3，遍历
        for(int i = start; i < start + 3; ++i)
        {
            num = num * 10 + s[i] - '0';    // 当前这段 ip 的数字
            if(num > 255)                    // 如果值超过 255，则不合法，直接返回
                return;
            segments[segIdx] = num;            
            backTrack(s, i + 1, segIdx + 1);    // 递归回溯
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_COUNT);
        backTrack(s, 0, 0);
        return resultList;
    }
};

复杂度分析：设字符串长度 N

时间复杂度 O()：IP 地址一共 4 段，每段一共 3 种情况（1、2、3 位数字），因此一共种状态，而每一种状态如果最终是有效的，就要拷贝存储到结果数组，时间复杂度 O(N)
空间复杂度 O(4)：递归深度为 4，且 segments 数组长度为 4

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.5 MB, 在所有 C++ 提交中击败了 34.87% 的用户

hot 100

[中等] 93. 复原 IP 地址

题目

解答 & 代码