力扣93题：复原 IP 地址

力扣93题：复原 IP 地址（C语言实现详解）

题目描述

给定一个只包含数字的字符串 s，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址需满足以下条件：

1. IP 地址由四个整数（每个整数位于 0 到 255 之间）组成，用 ‘.’ 分隔；
2. 每个整数不能包含前导零（如 “01” 是无效的，但 “0” 是有效的）。

示例 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. 状态定义：
   每次递归处理当前字符串片段，尝试将其分割为一个有效的 IP 地址部分。

2. 剪枝条件：

   • 剩余的字符长度不够或过长，直接返回。
   • 当前片段值不在 0 到 255 之间，或者包含前导零时，跳过该分支。

3. 递归结束条件：
   当找到 4 个有效的 IP 地址段且遍历完整个字符串时，将结果加入解集中。

---

C语言实现

以下是基于上述思路的代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 辅助函数：检查字符串是否为合法的 IP 段
int isValidSegment(const char *s, int start, int end) {if (start > end) return 0;// 如果有前导零且长度大于 1，则无效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; // 超出范围}return 1;
}// 回溯函数
void backtrack(char *s, int start, int segment, char *currentIP, int currentLen, char **result, int *returnSize) {int n = strlen(s);// 如果找到 4 段且刚好用完所有字符if (segment == 4 && start == n) {currentIP[currentLen - 1] = '\0'; // 去掉末尾的 '.'result[*returnSize] = strdup(currentIP); // 保存结果(*returnSize)++;return;}// 剩余字符不足或超出范围，剪枝if (segment == 4 || start == n) return;// 尝试分割 1 到 3 个字符作为当前段for (int len = 1; len <= 3; len++) {if (start + len - 1 >= n) break; // 超出字符串范围if (!isValidSegment(s, start, start + len - 1)) continue; // 非法段// 在 currentIP 中添加当前段strncpy(currentIP + currentLen, s + start, len);currentIP[currentLen + len] = '.'; // 添加 '.'// 递归处理下一段backtrack(s, start + len, segment + 1, currentIP, currentLen + len + 1, result, returnSize);}
}// 主函数
char **restoreIpAddresses(char *s, int *returnSize) {*returnSize = 0;int n = strlen(s);// 最多 27 个有效 IP（假设最大输入为 "255255255255"）char **result = (char **)malloc(27 * sizeof(char *));char currentIP[20]; // 暂存当前 IPif (n < 4 || n > 12) return result; // 长度不合法，直接返回backtrack(s, 0, 0, currentIP, 0, result, returnSize);return result;
}// 测试函数
int main() {char s[] = "25525511135";int returnSize;char **result = restoreIpAddresses(s, &returnSize);printf("有效的 IP 地址有：\n");for (int i = 0; i < returnSize; i++) {printf("%s\n", result[i]);free(result[i]); // 释放内存}free(result); // 释放内存return 0;
}

---

测试用例

示例 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. 校验合法性函数

int isValidSegment(const 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; // 超范围}return 1;
}

2. 回溯处理

void backtrack(char *s, int start, int segment, char *currentIP, int currentLen, char **result, int *returnSize) {if (segment == 4 && start == strlen(s)) {currentIP[currentLen - 1] = '\0';result[*returnSize] = strdup(currentIP);(*returnSize)++;return;}if (segment == 4 || start == strlen(s)) return;for (int len = 1; len <= 3; len++) {if (start + len - 1 >= strlen(s)) break;if (!isValidSegment(s, start, start + len - 1)) continue;strncpy(currentIP + currentLen, s + start, len);currentIP[currentLen + len] = '.';backtrack(s, start + len, segment + 1, currentIP, currentLen + len + 1, result, returnSize);}
}

---

复杂度分析

1. 时间复杂度：
   每次递归最多有 $3^4$ 种可能，字符串校验时间为 $O(1)$，故总时间复杂度为 $O(3^4)$。

2. 空间复杂度：
   递归调用栈深度为 $O(4)$，临时数组存储 IP 地址段，额外空间复杂度为 $O(n)$。