93. 复原 IP 地址（力扣LeetCode）

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

示例 1：

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

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

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

提示：

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

回溯算法

注意：这段代码中使用了一个string path来存入当前正在构建的 IP 地址，存的时候是如果符合条件就直接存入了，所以回溯的时候要整段的回溯，即整段的删除

正确如下：

// 保存当前路径，以便之后进行恢复
string temp = path;

//符合条件就整段存入
path += s.substr(start, i - start + 1);
path += '.';

// 继续递归，尝试找到下一部分
backstracking(s, i + 1, count);

// 整段回溯，恢复到上一步的路径和点的数量
path = temp;
1
2
3
4
5
6
7
8
9
10
11
12

错误回溯如下：

path+=(s.substr(start,i-start+1));
path+='.';
backstracking(s,i+1,count);
if(path.back()=='.')
    path.pop_back();
path.pop_back();
1
2
3
4
5
6

举例说明：

假设给定的字符串为 "25525511135"，并且我们正在尝试构造有效的IP地址。我们从空路径path开始并逐步构建它。

当我们第一次调用backstracking函数时，path为空，count为0。

我们逐步试探这个字符串的不同部分，看看是否可以构成IP地址的一个段。例如，我们首先尝试 "255" 作为IP地址的第一个部分，所以path变为 "255." 并且count变为1。

现在我们递归调用backstracking，它会继续向path中添加新的段。如果我们再次添加 "255"，path现在就是 "255.255." 并且count是2。

继续这个递归过程，让我们假设第三段是 "11"，那么path会变成 "255.255.11." 并且count是3。

然后我们添加最后一个段 "135"，path完成为 "255.255.11.135"。现在我们找到了一个有效的IP地址，它会被添加到result中。

在添加到result之后，我们需要返回到上一个状态，也就是 "255.255.11."，以便尝试其他可能的IP地址段。为了做到这一点，我们需要恢复path到它在添加最后一个段之前的状态。这就是所谓的回溯，它允许我们“撤销”最后一步并尝试另一条路。

在原始代码中，作者尝试用path.pop_back()来实现这一点，但这种方法不可靠，因为它只能移除path末尾的一个字符。如果最后一个段包含多个字符，比如 "135"，单纯调用pop_back()一次并不能恢复到 "255.255.11."。这就是为什么我们需要记录当前状态到一个临时变量（在这里是temp），并在递归调用返回后，使用这个临时变量来恢复path。

正确的做法是在递归前保存path的当前值，然后无论添加了多少字符，在递归结束后都能正确地恢复原始状态。这就是为什么我们在上面的修正代码中使用:

string temp = path;
// ...在递归中添加字符到path...
path = temp; // 在递归结束后恢复path的原始状态
1
2
3

这样无论path添加了多少个字符，我们都能通过简单地将path重新赋值为temp来恢复到递归调用之前的状态。

完整代码如下：

class Solution {
public:
    // 主函数，接受一个字符串作为输入，返回所有可能的有效 IP 地址
    vector<string> restoreIpAddresses(string s) {
        backstracking(s, 0, 0);  // 调用辅助函数开始回溯过程
        return result;  // 返回存储所有有效 IP 地址的结果
    }

private:
    vector<string> result;  // 存储所有可能的有效 IP 地址
    string path;  // 存储当前正在构建的 IP 地址

    // 辅助函数，用于检查字符串 s 的一个子串是否可以成为 IP 地址的一部分
    bool cheak(string& s, int begin, int end) {
        // 如果开始位置大于结束位置，返回false
        if (begin > end) return false;
        // 如果子串以 '0' 开头且长度大于1，返回false（防止前导0）
        if (s[begin] == '0' && begin != end) return false;
        // 用于计算子串的数值
        int sum = 0;
        for (int i = begin; i <= end; i++) {
            // 如果字符不是数字，返回false
            if (s[i] > '9' || s[i] < '0') return false;
            // 将字符转换为数字并累加到 sum
            sum = sum * 10 + (s[i] - '0');
            // 如果累计的数值大于255，返回false（IP地址的每部分应在0-255之间）
            if (sum > 255) return false;
        }
        // 子串是IP地址的一个有效部分
        return true;
    }

    // 辅助函数，用于进行回溯
    void backstracking(string& s, int start, int count) {
        // 如果已经找到3个点，此时应检查最后一部分是否有效
        if (count == 3) {
            // 检查最后一部分是否有效
            if (cheak(s, start, s.size() - 1)) {
                // 如果有效，将其添加到当前路径末尾
                path += s.substr(start);
                // 将当前完整路径加入到结果集
                result.push_back(path);
            }
            // 无论最后一部分是否有效，到此为止都应该返回
            return;
        }
        // 遍历字符串的每一部分
        for (int i = start; i < s.size(); i++) {
            // 检查从start到i的子串是否有效
            if (cheak(s, start, i)) {
                // 保存当前路径，以便之后进行恢复
                string temp = path;
                // 将有效的子串加入到当前路径
                path += s.substr(start, i - start + 1);
                // 加入点分隔符
                path += '.';
                count++;  // 增加点的数量，表示找到了IP地址的一部分
                // 继续递归，尝试找到下一部分
                backstracking(s, i + 1, count);
                // 回溯，恢复到上一步的路径和点的数量
                path = temp;
                count--;
            } else {
                // 一旦发现子串不再有效，就中断循环
                break;
            }
        }
    }
};

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

这段代码实现了一个回溯算法，用以搜索并构建所有可能的有效IP地址组合。主函数restoreIpAddresses初始化回溯过程，私有成员result和path分别用来存储最终结果和当前构造的IP地址。私有函数cheak用于验证给定字符串的子串是否为有效的IP地址段，而backstracking是一个递归函数，负责穷举并检查所有可能的IP地址组合。

回溯优化（在原s字符串上操作）

// 93. 复原 IP 地址
class Solution {
public:
    // 主函数，接受一个字符串作为输入，返回所有可能的有效 IP 地址
    vector<string> restoreIpAddresses(string s) {
        // 如果字符串长度不适合构成IP地址，直接返回空结果
        if(s.size() < 4 || s.size() > 12) return result;
        // 开始回溯搜索过程
        backstracking(s, 0, 0);
        // 返回找到的所有有效IP地址
        return result;
    }

private:
    // 用于存储所有找到的有效IP地址的结果数组
    vector<string> result;

    // 辅助函数，用于检查字符串s的部分是否可以成为IP地址的一部分
    // start为部分的起始索引，end为部分的结束索引
    bool check(string& s, int start, int end) {
        // 如果起始索引大于结束索引，表示这是一个空部分，返回false
        if(start > end) return false;
        // 如果部分以'0'开头并且长度大于1，表示有前导零，返回false
        if(s[start] == '0' && start != end) return false;
        // 用于计算部分的数值
        int sum = 0;
        for(int i = start; i <= end; i++) {
            // 如果字符不是数字，返回false
            if(s[i] < '0' || s[i] > '9') return false;
            // 把字符转为数字并加到sum
            sum = sum * 10 + (s[i] - '0');
            // 如果数值大于255，返回false
            if(sum > 255) return false;
        }
        // 部分是IP地址的一个有效段落
        return true;
    }

    // 一个递归函数，用于进行回溯搜索
    // s是原始字符串的引用，start是当前处理的起始位置，count是到目前为止添加的点分隔符数量
    void backstracking(string& s, int start, int count) {
        // 如果已经添加了3个点分隔符
        if(count == 3) {
            // 检查剩余部分是否构成有效的IP地址的最后一部分
            if(check(s, start, s.size() - 1)) {
                // 如果是，添加到结果中
                result.push_back(s);
            }
            // 已经检查完最后一部分，返回上一层
            return;
        }
        // 遍历字符串的每个可能的部分
        for(int i = start; i < s.size(); i++) {
            // 检查当前部分是否有效
            if(check(s, start, i)) {
                // 在当前部分的下一个位置插入点分隔符
                s.insert(s.begin() + i + 1, '.');
                // 递归调用，处理下一部分，起始位置是当前位置的下两个（因为添加了点分隔符）
                // 并增加点分隔符的数量
                backstracking(s, i + 2, count + 1);
                // 回溯：删除刚刚添加的点分隔符，恢复字符串
                s.erase(s.begin() + i + 1);
            } else {
                // 一旦找到无效部分，终止循环
                break;
            }
        }
    }
};
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

此代码定义了一个名为Solution的类，其包含用于找到所有有效IP地址的方法。这个问题的关键在于能够通过插入点分隔符来划分给定的数字字符串。首先，它会在主函数中检查输入字符串s的长度是否符合构造IP地址的基本要求。然后，使用递归回溯函数backstracking来尝试所有可能的点分隔符插入位置，从而形成有效的IP地址段。check函数用来验证每一段是否符合IP地址的规则。当构造完一个IP地址（即插入了3个点）后，它会在result数组中记录下来。最终，主函数返回包含所有可能有效IP地址的result数组。