{x}
blog image

Compare Version Numbers

Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros.

To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0.

Return the following:

  • If version1 < version2, return -1.
  • If version1 > version2, return 1.
  • Otherwise, return 0.

 

Example 1:

Input: version1 = "1.2", version2 = "1.10"

Output: -1

Explanation:

version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

Example 2:

Input: version1 = "1.01", version2 = "1.001"

Output: 0

Explanation:

Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 3:

Input: version1 = "1.0", version2 = "1.0.0.0"

Output: 0

Explanation:

version1 has less revisions, which means every missing revision are treated as "0".

 

Constraints:

  • 1 <= version1.length, version2.length <= 500
  • version1 and version2 only contain digits and '.'.
  • version1 and version2 are valid version numbers.
  • All the given revisions in version1 and version2 can be stored in a 32-bit integer.

Solution Explanation

This problem involves comparing two version numbers represented as strings. The version numbers are composed of revisions separated by dots (.). The goal is to determine if version1 is less than, greater than, or equal to version2.

The solution uses a two-pointer approach to iterate through the revisions of both version strings simultaneously. Each revision is parsed as an integer, ignoring leading zeros. The comparison is done revision by revision. If a difference is found, the function returns -1 if version1's revision is smaller and 1 if it's larger. If all revisions are equal, it returns 0. If one string has fewer revisions than the other, the missing revisions are treated as 0.

Algorithm

  1. Initialization: Two pointers, i and j, are initialized to 0, pointing to the beginning of version1 and version2 respectively.

  2. Iteration: The while loop continues as long as either i or j is less than the length of its respective string.

  3. Revision Parsing: Inside the loop, two variables a and b are used to store the integer values of the current revisions being compared. Inner while loops extract the digits from the strings until a dot (.) is encountered or the end of the string is reached.

  4. Comparison: If a and b are different, the function immediately returns -1 if a < b (version1 < version2) and 1 if a > b (version1 > version2).

  5. Pointer Increment: After comparing the revisions, the pointers i and j are incremented to move to the next revisions. Incrementing i and j by 1 accounts for moving past the ..

  6. Equal Versions: If the loop completes without finding any difference between revisions, it means the versions are equal, and the function returns 0.

Time and Space Complexity Analysis

  • Time Complexity: O(M + N), where M and N are the lengths of version1 and version2 respectively. The algorithm iterates through each character of both strings at most once.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. It only uses a few integer variables to store the current revision values.

Code Examples (Refer to the markdown output for code in multiple languages)

The provided markdown output contains the code implementations in Python3, Java, C++, Go, TypeScript and C#. All implementations follow the algorithm described above. The core logic remains consistent across all languages, but syntax and standard library functions differ slightly.