【力扣刷题练习】93. 复原 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 中的任何数字。你可以按 任何 顺序返回答案。

题目解答：

class Solution {
private:
    vector<string> res; // 创建容器储存结果
    // 回溯的主体
    void backtrack(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isLegal(s, startIndex, s.size() - 1))
                res.push_back(s);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isLegal(s, startIndex, i)) {
                s.insert(s.begin() + i + 1, '.');
                pointNum++;
                backtrack(s, i + 2, pointNum);
                pointNum--;
                s.erase(s.begin() + i + 1);
            } else {
                break;
            }
        }
    }

    // 判断该串在给定区间内组成数字是否合法
    bool isLegal(string s, int start, int end) {
        if (start > end || (s[start] == '0' && start != end))
            return false;
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0')
                return false;
            num = num * 10 + (s[i] - '0');
            if (num > 255)
                return false;
        }
        return true;
    }

public:
    vector<string> restoreIpAddresses(string s) {
        res.clear();
        if (s.size() >= 4 && s.size() <= 12) // 长度符合ip地址规则
            backtrack(s, 0, 0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

题目思路：

1. 私有成员变量：

   • vector res;：用于存储所有可能的合法 IP 地址。

2. 回溯函数 backtrack：

   • 参数：
     • string& s：输入的字符串。
     • int startIndex：当前处理位置的起始索引。
     • int pointNum：当前已经插入的点号数量。
   • 功能：递归地尝试在字符串 s 的不同位置插入点号，以生成可能的 IP 地址。
   • 终止条件：当已经插入了 3 个点号（即 IP 地址的 4 部分都已经形成），并且当前的字符串 s 在 startIndex 到末尾的部分是一个合法的数字时，将 s 添加到结果集 res 中。
   • 递归过程：从 startIndex 开始遍历字符串 s，尝试在每个位置插入点号。如果插入点号后的子串是合法的数字，则递归调用 backtrack 函数继续处理剩余部分。

3. 辅助函数 isLegal：

   • 参数：
     • string s：输入的字符串。
     • int start：检查的起始索引。
     • int end：检查的结束索引。
   • 功能：判断字符串 s 在 start 到 end 的子串是否表示一个合法的数字（在 IP 地址的上下文中）。
   • 判断逻辑：
     • 如果子串的长度超过 3 或以 ‘0’ 开头但不是单个 ‘0’，则不合法。
     • 遍历子串的每个字符，如果字符不是数字，则不合法。
     • 计算子串表示的数字，如果数字大于 255，则不合法。

4. 公有函数 restoreIpAddresses：

   • 参数：
     • string s：输入的字符串。
   • 功能：主函数，用于启动整个恢复 IP 地址的过程。
   • 首先，清空结果集 res。
   • 检查输入字符串 s 的长度，确保它符合 IP 地址的长度规则（4 到 12 个字符）。
   • 调用 backtrack 函数开始回溯过程。
   • 返回结果集 res。

通过回溯算法，尝试在输入字符串的不同位置插入点号，以生成所有可能的合法 IP 地址组合。在每次尝试插入点号时，都通过 isLegal 函数来检查当前部分是否是一个合法的数字。