html商城网站模板下载,沈阳建设工程信息网官方网站,湖南品牌网站建设,网络综合布线系统设计方案力扣93题#xff1a;复原 IP 地址#xff08;C语言实现详解#xff09;
题目描述
给定一个只包含数字的字符串 s#xff0c;复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址需满足以下条件#xff1a;
IP 地址由四个整数#xff08;每个整数位于 0 到 255 之间…力扣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假设最大输入为 255255255255char **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)。
