93. 复原IP地址

yzhms

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

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

yzhms

1. int getInt(char *s, int pos, int byteCnt)
   
2. {
   
3.     char tmp[4];
   
4.     if (byteCnt > 3) {
   
5.         return 0;
   
6.     }
   
7.     memcpy(tmp, &s[pos], byteCnt);
   
8.     tmp[byteCnt] = 0;
   
9.     return atoi(tmp);
   
10. }
    
11. 
    
12. void step(char* s, int index, int pos, int byteCnt, char **result, int *returnSize, int* tmp)
    
13. {
    
14.     int len = strlen(&s[pos]);
    
15.     int size = 17;
    
16.     if ((len < byteCnt) || (index > 3) || ((len - byteCnt) > ((4 - index - 1) * 3))) {
    
17.         return;
    
18.     }
    
19.     if ((index == 3) && (len != byteCnt)) {
    
20.         return;
    
21.     }
    
22.     if (byteCnt == 3) {
    
23.         if ((s[pos] > '2') || ((s[pos] == '2') && (s[pos + 1] > '5')) || ((s[pos] == '2') && (s[pos + 1] == '5') && (s[pos + 2] > '5'))) {
    
24.             return;
    
25.         }
    
26.     }
    
27.     if ((s[pos] == '0') && (byteCnt > 1)) {
    
28.         return;
    
29.     }
    
30.     tmp[index] = getInt(s, pos, byteCnt);
    
31.     if (index == 3) {
    
32.         result[*returnSize] = (char*)malloc(size);
    
33.         snprintf(result[*returnSize], size - 1, "%d.%d.%d.%d", tmp[0], tmp[1], tmp[2], tmp[3]);
    
34.         result[*returnSize][size - 1] = 0;
    
35.         (*returnSize)++;
    
36.     } else {
    
37.         step(s, index + 1, pos + byteCnt, 1, result, returnSize, tmp);
    
38.         step(s, index + 1, pos + byteCnt, 2, result, returnSize, tmp);
    
39.         step(s, index + 1, pos + byteCnt, 3, result, returnSize, tmp);
    
40.     }
    
41. }
    
42. 
    
43. /**
    
44. * Note: The returned array must be malloced, assume caller calls free().
    
45. */
    
46. char ** restoreIpAddresses(char * s, int* returnSize){
    
47.     int resultCnt = 0;
    
48.     char **result;
    
49.     int tmp[4] = {0, 0, 0, 0};
    
50. 
    
51.     if (!s || !s[0] || !returnSize) {
    
52.         if (returnSize) {
    
53.             *returnSize = 0;
    
54.         }
    
55.         return NULL;
    
56.     }
    
57.     result = (char**)malloc(81 * sizeof(char*));
    
58.     *returnSize = 0;
    
59.    
    
60.     step(s, 0, 0, 1, result, returnSize, tmp);
    
61.     step(s, 0, 0, 2, result, returnSize, tmp);
    
62.     step(s, 0, 0, 3, result, returnSize, tmp);
    
63.     return result;
    
64. }

复制代码

执行结果：通过
显示详情

执行用时 :4 ms, 在所有 C 提交中击败了70.47%的用户
内存消耗 :6 MB, 在所有 C 提交中击败了100.00%的用户