leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

restore_ip_addr.c (2410B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 93. Restore IP Addresses
#include "leetcode.h"

/*
 * a valid ip address consists of exactly 4 integers separated by single dots
 * each integer is between 0 and 255 (inclusive) and cannot have leading 0's
 * given: string 's' containing only digits, return all possible valid ip
 * addresses that can be formed by insert dots into 's'. digits cannot be
 * reordered or removed. return addresses in any order.
 */

char **restoreIpAddresses(char *s, int *returnSize) {
  int n = strlen(s), capacity = 0;
  char **ans = NULL;
  *returnSize = 0;
  for (int a = 1; a <= 3 && a + 2 < n && (1 == a || '0' != s[0]) &&
                  (a < 3 || 0 > memcmp(s, "256", 3));
       ++a) {
    for (int b = a + 1;
         b <= a + 3 && b + 1 < n && (a + 1 == b || '0' != s[a]) &&
         (b < a + 3 || 0 > memcmp(s + a, "256", 3));
         ++b) {
      for (int c = b + 1; c <= b + 3 && c < n && (b + 1 == c || '0' != s[b]) &&
                          (c < b + 3 || 0 > memcmp(s + b, "256", 3));
           ++c) {
        if (c + 3 >= n && (c + 1 == n || '0' != s[c]) &&
            (n < c + 3 || 0 > memcmp(s + c, "256", 3))) {
          if (*returnSize >= capacity) {
            capacity = capacity ? capacity * 2 : 1;
            ans = (char **)realloc(ans, capacity * sizeof(char *));
          }
          char *dest = (char *)malloc((n + 4) * sizeof(char));
          memcpy(dest, s, a);
          dest[a] = '.';
          memcpy(dest + a + 1, s + a, b - a);
          dest[b + 1] = '.';
          memcpy(dest + b + 2, s + b, c - b);
          dest[c + 2] = '.';
          memcpy(dest + c + 3, s + c, n - c);
          dest[n + 3] = '\0';
          ans[(*returnSize)++] = dest;
        }
      }
    }
  }
  return ans;
}

int main() {
  char *s1 = "25525511135", *s2 = "0000", *s3 = "101023";
  int rs1, rs2, rs3;
  char **ria1 = restoreIpAddresses(s1, &rs1);
  char **ria2 = restoreIpAddresses(s2, &rs2);
  char **ria3 = restoreIpAddresses(s3, &rs3);
  for (int i = 0; i < rs1; i++)
    printf("%s ", ria1[i]); // expect: ["255.255.11.135","255.255.111.35"]
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%s ", ria2[i]); // expect: ["0.0.0.0"]
  printf("\n");
  for (int i = 0; i < rs3; i++)
    printf(
        "%s ",
        ria3[i]); // expect:
                  // ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
  printf("\n");
  free(ria1);
  free(ria2);
  free(ria3);
}