aboutsummaryrefslogtreecommitdiff
path: root/restore_ip_addr.c
blob: e814691972745a6cfa58667286f2b6086314f98c (plain)
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
71
72
73
74
// 93. Restore IP Addresses
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define IN_RANGE(c, m, n) ((c) >= (m) && c <= (n))

/*
 * 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.
 */

int isValidPart(char *s, int l) {
  switch (l) {
  case 1:
    return IN_RANGE(s[0], '0', '9');
    break;
  case 2:
    return IN_RANGE(s[0], '1', '9') && IN_RANGE(s[1], '0', '9');
    break;
  case 3:
    return (s[0] == '1' && IN_RANGE(s[1], '0', '9') &&
            IN_RANGE(s[2], '0', '9')) ||
           (s[0] == '2' &&
            (IN_RANGE(s[1], '0', '4') && IN_RANGE(s[2], '0', '9') ||
             s[1] == '5' && IN_RANGE(s[2], '0', '5')));
    break;
  default:
    return 0;
  }
}

char *getAddr(char *s, int l, int a, int b, int c) {
  if (isValidPart(s, a) && isValidPart(s + a, b - a) &&
      isValidPart(s + b, c - b) && isValidPart(s + c, l - c)) {
    char *addr = malloc(sizeof(char) * (l + 4));
    memcpy(addr, s, a);
    memcpy(addr + a + 1, s + a, b - a);
    memcpy(addr + b + 2, s + b, c - b);
    memcpy(addr + c + 3, s + c, l - c);
    addr[a] = addr[b + 1] = addr[c + 2] = '.';
    addr[l + 3] = '\0';
    return addr;
  } else
    return NULL;
}

char **restoreIpAddresses(char *s, int *returnSize) {
  *returnSize = 0;
  int l = strlen(s), a, b, c;
  if (l < 4 || l > 12)
    return NULL;
  char **addrs = malloc(sizeof(char *) * ((l - 1) * (l - 2) * (l - 3) / 6)),
       *addr;
  for (a = 1; a < 4; a++) {
    if (a > l - 3 || a < l - 9)
      continue;
    for (b = a + 1; b < a + 4; b++) {
      if (b > l - 2 || b < l - 6)
        continue;
      for (c = b + 1; c < b + 4; c++) {
        if (c > l - 1 || c < l - 3)
          continue;
        if (addr = getAddr(s, l, a, b, c))
          addrs[(*returnSize)++] = addr;
      }
    }
  }
  return addrs;
}

int main() { char s1[] = {"25525511135"}, s2[] = {"0000"}, s3[] = {"101023"}; }