【力扣刷题练习】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. 私有成员变量：

   • vector<string> 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 函数来检查当前部分是否是一个合法的数字。