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

165 - Compare Version Numbers

Question

Algorithm

Code

All Problems

All Solutions