aboutsummaryrefslogtreecommitdiff
path: root/compare_version_num.c
blob: eaa3fed12f54021a4f15110dadaf6c1d50e8a042 (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
75
76
77
78
79
80
81
82
83
84
// 165. Compare Version Numbers
#include "leetcode.h"

/*
 * given two version numbers 'version1' and 'version2', compare them. version
 * numbers consist of one or more revisions joined by a dot. each revision
 * consists of digits and may contain leading zeros. every revision contains at
 * least one character. revisions are 0-indexed from left to right, right the
 * leftmost revision being revision 0, the next revision being revision 1, and
 * so on. to compare version numbers, use the following rules. if 'version1 <
 * version2' return -1, if 'version1 > version2' return 1, otherwise, return 0
 */

int count_dot(char *s, int n) {
  int dot = 0;
  for (int i = 0; i < n; i++)
    if (s[i] == '.')
      dot++;
  return dot;
}

void helper(char *s, int n, int *data) {
  int val = 0, idx = 0;
  for (int i = 0; i < n; i++)
    if (s[i] == '.') {
      data[idx] = val;
      idx++;
      val = 0;
    } else {
      val = val * 10 + s[i] - '0';
    }
  data[idx] = val;
}

int compareVersion(char *version1, char *version2) {
  int n1 = strlen(version1), n2 = strlen(version2);
  int p1 = 0, p2 = 0, ans = 0;
  int item1 = count_dot(version1, n1) + 1;
  int item2 = count_dot(version2, n2) + 1;
  int *data1 = (int *)malloc(item1 * sizeof(int));
  int *data2 = (int *)malloc(item2 * sizeof(int));
  helper(version1, n1, data1);
  helper(version2, n2, data2);
  while (p1 < item1 || p2 < item2) {
    if (p1 == item1) {
      for (int i = p2; i < item2; i++)
        if (!data2[i]) {
          ans = -1;
          goto exit;
        }
      ans = 0;
      goto exit;
    } else if (p2 == item2) {
      for (int i = p1; i < item1; i++)
        if (!data1[i]) {
          ans = 1;
          goto exit;
        }
      ans = 0;
      goto exit;
    } else {
      if (data1[p1] > data2[p2]) {
        ans = 1;
        goto exit;
      }
      if (data1[p1] < data2[p2]) {
        ans = -1;
        goto exit;
      }
      p1++, p2++;
    }
  }
exit:
  free(data1), free(data2);
  return ans;
}

int main() {
  char *v11 = "1.01", *v21 = "1.001", *v12 = "1.0", *v22 = "1.0.0",
       *v13 = "0.1", *v23 = "1.1";
  printf("%d\n", compareVersion(v11, v21)); // expect: 0
  printf("%d\n", compareVersion(v12, v22)); // expect: 0
  printf("%d\n", compareVersion(v13, v23)); // expect: -1
}