165. Compare Version Numbers

MediumLeetCode

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.

How to solve the problem

• Split and Compare Approach
• Two Pointers Approach

Code

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        num1 = [int(x) for x in version1.split('.')]
        num2 = [int(x) for x in version2.split('.')]

        l1 = len(num1)
        l2 = len(num2)
        for i in range(max(l1,l2)):
            if i < l1:
                n1 = num1[i]
            else: n1 = 0
            if i < l2:
                n2 = num2[i]
            else: n2 = 0
            if n1 != n2:
                if n1 > n2:
                    return 1
                else: return -1
        return 0

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        num1 = [int(x) for x in version1.split('.')]
        num2 = [int(x) for x in version2.split('.')]

        l1 = len(num1)
        l2 = len(num2)
        for i in range(max(l1,l2)):
            n1 = num1[i] if i < l1 else 0
            n2 = num2[i] if i < l2 else 0
            if n1 != n2:
                if n1 > n2:
                    return 1
                else: return -1
        return 0

Complexity

• Approach: Split and Compare Approach

• Time complexity: O(n + m)

  • Where n and m are the lengths of version1 and version2. We need to split both strings, convert substrings to integers, and compare at most max(revisions1, revisions2) pairs.

• Space complexity: O(n + m)

  • We store the split versions in arrays, where the space is proportional to the number of revisions in each version string.