leetcode做题笔记93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

思路一：递归

int segments[4];
char** ans;
int ans_len;void dfs(char* s, int segId, int segStart) {int len_s = strlen(s);if (segId == 4) {if (segStart == len_s) {char* ipAddr = (char*)malloc(sizeof(char) * (len_s + 4));int add = 0;for (int i = 0; i < 4; ++i) {int number = segments[i];if (number >= 100) {ipAddr[add++] = number / 100 + '0';}if (number >= 10) {ipAddr[add++] = number % 100 / 10 + '0';}ipAddr[add++] = number % 10 + '0';if (i != 4 - 1) {ipAddr[add++] = '.';}}ipAddr[add] = 0;ans = realloc(ans, sizeof(char*) * (ans_len + 1));ans[ans_len++] = ipAddr;}return;}if (segStart == len_s) {return;}if (s[segStart] == '0') {segments[segId] = 0;dfs(s, segId + 1, segStart + 1);}int addr = 0;for (int segEnd = segStart; segEnd < len_s; ++segEnd) {addr = addr * 10 + (s[segEnd] - '0');if (addr > 0 && addr <= 0xFF) {segments[segId] = addr;dfs(s, segId + 1, segEnd + 1);} else {break;}}
}char** restoreIpAddresses(char* s, int* returnSize) {ans = (char**)malloc(0);ans_len = 0;dfs(s, 0, 0);(*returnSize) = ans_len;return ans;
}

分析：

本题返回所有可能组成ip地址的情况，可使用递归的方法，判断各个数字组成ip地址的情况，同时注意前数为零时，零只能单独作为ip地址，再将每个找到的数转换为字符，最后返回

总结：

本题考察递归的应用，将每个数可能组成地址的情况列举出来即可得到答案