165. Compare Version Numbers

Description

The problem is to compare two version numbers, version1 and version2, which are given as strings. Each version string consists of several levels separated by dots (e.g., "1.0.1"). Each level in the version is an integer that might contain leading zeros. The task is to determine which version is greater, or if they are equal, by comparing the integers at each corresponding level.

The possible outcomes are:

• Return 1 if version1 is greater than version2.
• Return -1 if version1 is less than version2.
• Return 0 if both versions are equal.

Intuition

To compare the versions, we can break each version string into its individual levels, compare the corresponding levels one by one, and determine which version is greater based on the first non-equal level. If all levels are equal, then the versions are equal. By treating each level as an integer, we can avoid complications due to leading zeros.

Approach

1. Helper Function: - Create a helper function to parse and return the integer value of a level starting from a given index in the version string, stopping when a dot . or the end of the string is encountered.
2. Iterate Through Both Versions: - Initialize two pointers i and j to traverse through version1 and version2. - Use the helper function to extract and compare each level from version1 and version2. - If the current level from version1 is greater than that from version2, return 1. - If the current level from version1 is less than that from version2, return -1. - Move the pointers to the next level and repeat.
3. Return Result: - If all levels are equal after the loop, return 0 to indicate that the versions are equal.

Complexity

Time Complexity:

O(n + m), where n is the length of version1 and m is the length of version2. Each character in both version strings is processed once.

Space Complexity:

O(1). The algorithm uses a constant amount of extra space, aside from the input strings.

Code

C++

class Solution {
public:
    int compareVersion(string version1, string version2) {
        auto helper = [](const string& s, int& idx) {
            int num = 0;
            while (idx < s.size()) {
                if (s[idx] == '.') break;
                else num = num * 10 + (s[idx] - '0');
                idx++;
            }
            return num;
        };

        int i = 0, j = 0;
        while (i < version1.size() || j < version2.size()) {
            int v1 = (i < version1.size()) ? helper(version1, i) : 0;
            int v2 = (j < version2.size()) ? helper(version2, j) : 0;

            if (v1 > v2) return 1;
            else if (v1 < v2) return -1;

            i++;
            j++;
        }

        return 0;
    }
};

Python

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        
        def helper(s: str, idx: int) -> (int, int):
            num = 0
            while idx < len(s):
                if s[idx] == '.':
                    break
                else:
                    num = num * 10 + int(s[idx])
                idx += 1
            return num, idx + 1

        i, j = 0, 0
        while i < len(version1) or j < len(version2):
            v1, i = helper(version1, i)
            v2, j = helper(version2, j)

            if v1 > v2:
                return 1
            elif v1 < v2:
                return -1

        return 0

Java

class Solution {
    public int compareVersion(String version1, String version2) {
        int i = 0, j = 0;

        while (i < version1.length() || j < version2.length()) {
            int v1 = 0, v2 = 0;

            while (i < version1.length() && version1.charAt(i) != '.') {
                v1 = v1 * 10 + (version1.charAt(i) - '0');
                i++;
            }

            while (j < version2.length() && version2.charAt(j) != '.') {
                v2 = v2 * 10 + (version2.charAt(j) - '0');
                j++;
            }

            if (v1 > v2) return 1;
            else if (v1 < v2) return -1;

            i++;
            j++;
        }

        return 0;
    }
}

JavaScript

var compareVersion = function(version1, version2) {
    
  const helper = function(s, idx) {
    let num = 0;
    while (idx < s.length) {
      if (s[idx] === '.') break;
      else num = num * 10 + parseInt(s[idx]);
      idx++;
    }
    return [num, idx + 1];
  };

  let i = 0, j = 0;
  while (i < version1.length || j < version2.length) {
    const [v1, next1] = helper(version1, i);
    const [v2, next2] = helper(version2, j);

    if (v1 > v2) return 1;
    else if (v1 < v2) return -1;

    i = next1;
    j = next2;
  }

  return 0;
};