165. Compare Version Numbers

Posted on | Edited on | Views:

https://leetcode.com/problems/compare-version-numbers/

Approach 1: Split + Parse, Two Pass, Linear Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int compareVersion(String version1, String version2) {
        String[] s1=version1.split("\\.");
        String[] s2=version2.split("\\.");
        
        int len=Math.max(s1.length,s2.length);
        for(int i=0;i<len;i++){
            int v1=i<s1.length?Integer.valueOf(s1[i]):0;
            int v2=i<s2.length?Integer.valueOf(s2[i]):0;
            if(v1!=v2) return v1>v2?1:-1;
        }
        return 0;
    }
}

Approach 2: Two Pointers, One Pass, Constant Space

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
class Pair<T1,T2>{
    T1 a;
    T2 b;
    Pair(T1 _a,T2 _b){a=_a;b=_b;}
    T1 getKey(){return a;}
    T2 getValue(){return b;}
}

class Solution {
    public Pair<Integer, Integer> getNextChunk(String version, int n, int p) {
      // if pointer is set to the end of string
      // return 0
      if (p > n - 1) {
        return new Pair<>(0, p);
      }
      // find the end of chunk
      int i, pEnd = p;
      while (pEnd < n && version.charAt(pEnd) != '.') {
        ++pEnd;
      }
      // retrieve the chunk
      // don't need to check pEnd with n-1
      i = Integer.parseInt(version.substring(p, pEnd));
      // find the beginning of next chunk
      p = pEnd + 1;
  
      return new Pair<>(i, p);
    }
  
    public int compareVersion(String version1, String version2) {
      int p1 = 0, p2 = 0;
      int n1 = version1.length(), n2 = version2.length();
  
      // compare versions
      int i1, i2;
      Pair<Integer, Integer> pair;
      while (p1 < n1 || p2 < n2) {
        pair = getNextChunk(version1, n1, p1);
        i1 = pair.getKey();
        p1 = pair.getValue();
  
        pair = getNextChunk(version2, n2, p2);
        i2 = pair.getKey();
        p2 = pair.getValue();
        if (i1 != i2) {
          return i1 > i2 ? 1 : -1;
        }
      }
      // the versions are equal
      return 0;
    }
  }

0%