力扣93题:复原 IP 地址(C语言实现详解)
题目描述
给定一个只包含数字的字符串 s
,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址需满足以下条件:
- IP 地址由四个整数(每个整数位于 0 到 255 之间)组成,用 ‘.’ 分隔;
- 每个整数不能包含前导零(如 “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"]
解题思路
此题可以通过回溯算法解决。
-
状态定义:
每次递归处理当前字符串片段,尝试将其分割为一个有效的 IP 地址部分。 -
剪枝条件:
- 剩余的字符长度不够或过长,直接返回。
- 当前片段值不在 0 到 255 之间,或者包含前导零时,跳过该分支。
-
递归结束条件:
当找到 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);}
}
复杂度分析
-
时间复杂度:
每次递归最多有 3 4 3^4 34 种可能,字符串校验时间为 O ( 1 ) O(1) O(1),故总时间复杂度为 O ( 3 4 ) O(3^4) O(34)。 -
空间复杂度:
递归调用栈深度为 O ( 4 ) O(4) O(4),临时数组存储 IP 地址段,额外空间复杂度为 O ( n ) O(n) O(n)。