每日一题——将数字字符串转化为IP地址

将数字字符串转化为IP地址 题目描述解题思路回溯法步骤分解 代码实现全局变量有效性验证函数回溯函数主函数完整代码 复杂度分析关键点说明总结 这题难度还挺大的，整体上实现并不容易。建议参考视频 和 programmercarl /0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html#%E6%80%9D%E8%B7%AF

题目描述

给定一个仅包含数字的字符串，将其转换为所有可能的有效IP地址形式。有效的IP地址由四个整数（0到255之间）构成，各部分用.分隔，且不能有前导零（除非该段本身为0）。

示例：

输入："25525522135" 输出：["255.255.22.135", "255.255.221.35"]

输入："000256" 输出：[]（因256超过255）

解题思路 回溯法 分割逻辑：IP地址由四段组成，需在字符串中找到三个分割点将字符串分为四段。有效性检查：每段必须满足： 值在0到255之间；无前导零（除非段本身为0）；仅包含数字。 递归终止条件：当分割点数量为3时，检查最后一段是否有效。剪枝：若当前分割无效，跳过后续尝试。 步骤分解 回溯函数：记录当前分割点位置和已分割段数。有效性验证：检查子串是否合法。生成结果：将合法分割组合成IP地址格式。

---

代码实现 全局变量 char** result; // 存储结果数组 int resultTop; // 结果数组当前索引 int segments[3]; // 记录三个分割点的位置 有效性验证函数 int isValid(char* s, int start, int end) { if (start > end) return 0; if (s[start] == '0' && start != end) return 0; // 前导零无效 int num = 0; for (int i = start; i <= end; i++) { if (s[i] < '0' || s[i] > '9') return 0; // 非数字字符 num = num * 10 + (s[i] - '0'); if (num > 255) return 0; // 超过255 } return 1; } 回溯函数 void backTracking(char* s, int startIndex, int pointNum) { if (pointNum == 3) { // 分割点已满3个 // 检查最后一段是否有效 if (isValid(s, startIndex, strlen(s) - 1)) { char* temp = (char*)malloc(strlen(s) + 4); // 分配新字符串内存 int count = 0, count1 = 0; for (int j = 0; j < strlen(s); j++) { temp[count++] = s[j]; // 在分割点后插入'.' if (count1 < 3 && j == segments[count1]) { temp[count++] = '.'; count1++; } } temp[count] = '\0'; // 扩展结果数组并保存 result = (char**)realloc(result, sizeof(char*) * (resultTop + 1)); result[resultTop++] = temp; } return; } for (int i = startIndex; i < strlen(s); i++) { if (isValid(s, startIndex, i)) { // 当前分割有效 segments[pointNum] = i; // 记录分割点 backTracking(s, i + 1, pointNum + 1); // 递归下一段 } else break; // 无效分割，剪枝 } } 主函数 char** restoreIpAddresses(char* s, int* returnSize) { result = (char**)malloc(0); resultTop = 0; backTracking(s, 0, 0); *returnSize = resultTop; return result; } 完整代码 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> char** result; // 用于存储所有可能的IP地址 int resultTop; // 当前result数组中的IP地址数量 // 记录应该加入'.'的位置，数组大小为3，因为IP地址有3个分隔点 int segments[3]; // 检查字符串是否为合法的IP段 // start和end分别表示当前检查的子字符串的起始和结束位置 int isValid(char* s, int start, int end) { // 如果起始位置大于结束位置，说明子字符串无效 if (start > end) { return 0; } // 如果子字符串以0开头且长度大于1，则该子字符串无效（例如01、001等） if (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'); // 将字符转换为数字并累加 // 如果数字大于255，则子字符串无效 if (num > 255) { return false; } } return true; // 如果通过所有检查，则子字符串有效 } // 回溯函数，用于生成所有可能的IP地址 // startIndex表示当前处理的字符串起始位置，pointNum表示当前已放置的'.'数量 void backTracking(char* s, int startIndex, int pointNum) { // 如果已放置3个'.'，说明已经生成了一个完整的IP地址 if (pointNum == 3) { // 检查最后一段字符串是否合法 if (isValid(s, startIndex, strlen(s) - 1)) { // 为存储当前IP地址分配内存 char* tempString = (char*)malloc(sizeof(char) * (strlen(s) + 4)); int count = 0; // 用于记录tempString的当前索引 int count1 = 0; // 用于记录已使用的'.'数量 // 遍历字符串，根据segments数组插入'.'生成IP地址 for (int j = 0; j < strlen(s); j++) { tempString[count++] = s[j]; // 将当前字符添加到tempString // 如果当前索引是'.'的位置，则插入'.'（最多插入3个） if (count1 < 3 && j == segments[count1]) { tempString[count++] = '.'; count1++; } } tempString[count] = '\0'; // 添加字符串结束符 // 扩容result数组以存储新的IP地址 result = (char**)realloc(result, sizeof(char*) * (resultTop + 1)); result[resultTop++] = tempString; // 将新生成的IP地址加入result } return; } // 遍历字符串，尝试将当前子字符串作为IP地址的一部分 for (int i = startIndex; i < strlen(s); i++) { // 检查当前子字符串是否合法 if (isValid(s, startIndex, i)) { // 记录当前'.'的位置 segments[pointNum] = i; // 递归处理下一段字符串 backTracking(s, i + 1, pointNum + 1); } else { // 如果当前子字符串不合法，则停止当前分支的搜索 break; } } } // 主函数，用于恢复IP地址 char** restoreIpAddresses(char* s, int* returnSize) { // 初始化result数组 result = (char**)malloc(0); resultTop = 0; // 开始回溯搜索 backTracking(s, 0, 0); *returnSize = resultTop; // 设置返回的IP地址数量 return result; }

---

复杂度分析 时间复杂度：O(n!)，回溯尝试所有可能分割方式。空间复杂度：O(n!)，存储所有可能的IP地址。

---

关键点说明 回溯终止条件：当分割点数为3时，验证最后一段。剪枝优化：遇到无效分割时立即终止当前循环。动态内存管理：结果字符串需动态分配，并适时扩展结果数组。

---

总结

通过回溯法遍历所有可能的分割方式，结合有效性剪枝，可高效生成所有合法IP地址。注意处理边界条件（如前导零、数值范围）和内存管理，确保程序健壮性。