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

这题难度还挺大的，整体上实现并不容易。建议参考视频
和https://programmercarl.com/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）

解题思路

回溯法

1. 分割逻辑：IP地址由四段组成，需在字符串中找到三个分割点将字符串分为四段。
2. 有效性检查：每段必须满足：
   • 值在0到255之间；
   • 无前导零（除非段本身为0）；
   • 仅包含数字。
3. 递归终止条件：当分割点数量为3时，检查最后一段是否有效。
4. 剪枝：若当前分割无效，跳过后续尝试。

步骤分解

1. 回溯函数：记录当前分割点位置和已分割段数。
2. 有效性验证：检查子串是否合法。
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地址。

---

关键点说明

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

---

总结

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