Question

Formatted question description: https://leetcode.ca/all/165.html

 165	Compare Version Numbers

 Compare two version numbers version1 and version2.
 If version1 > version2 return 1,
 if version1 < version2 return -1,
 otherwise return 0.

 You may assume that the version strings are non-empty and contain only digits and the .
 The . character does not represent a decimal point and is used to separate number sequences.
 For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

 Here is an example of version numbers ordering:

 0.1 < 1.1 < 1.2 < 13.37

Algorithm

Split by . and compare segment by segment.

Code

Java

  • 
    public class Compare_Version_Numbers {
    
        public static void main(String[] args) {
            Compare_Version_Numbers out = new Compare_Version_Numbers();
            Solution s = out.new Solution();
    
            System.out.println(s.compareVersion("1", "0"));
            System.out.println(s.compareVersion("1", "1.1"));
            // test case: "1", "1.1"
        }
    
    
        class Solution {
    
            public int compareVersion(String version1, String version2) {
    
                if (version1 == null || version2 == null || version1.length() == 0 || version2.length() == 0) {
                    return 0;
                }
    
                String[] list1 = version1.split("\\.");
                String[] list2 = version2.split("\\.");
    
                int length = Math.max(list1.length, list2.length);
                for (int i = 0; i < length; i++) {
    
                    Integer v1 = i < list1.length ? Integer.parseInt(list1[i]) : 0;
                    Integer v2 = i < list2.length ? Integer.parseInt(list2[i]) : 0;
    
                    int compare = v1.compareTo(v2);
    
                    if (compare != 0) {
                        return compare;
                    }
                }
    
                return 0;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/compare-version-numbers/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int compareVersion(string a, string b) {
            istringstream sa(a), sb(b);
            while (sa.good() || sb.good()) {
                string x, y;
                getline(sa, x, '.');
                getline(sb, y, '.');
                int v1 = x.size() ? stoi(x) : 0, v2 = y.size() ? stoi(y) : 0;
                if (v1 > v2) return 1;
                else if (v1 < v2) return -1;
            }
            return 0;
        }
    };
    
  • class Solution(object):
      def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        v1 = version1.split(".")
        v2 = version2.split(".")
        i = 0
        while i < len(v1) and i < len(v2):
          v1Seg, v2Seg = int(v1[i]), int(v2[i])
          if v1Seg > v2Seg:
            return 1
          elif v1Seg < v2Seg:
            return -1
          else:
            i += 1
        if i < len(v1) and int("".join(v1[i:])) != 0:
          return 1
        if i < len(v2) and int("".join(v2[i:])) != 0:
          return -1
        return 0
    
    

All Problems

All Solutions