Compare Version Numbers - Leetcode Solution

Problem Statement:

Given two version numbers, version1 and version2, compare them.

Version numbers consist of one or more revisions joined by a dot '.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example, 2.5.33 and 0.1 are valid version numbers.

To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.

Return the following:

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

Solution:

To solve this problem, we need to split both the versions into a list of integers and then compare each item of the two lists.

The first step is to split the versions into a list of integers at each '.' character. Then, for each index in the list, we compare the integer values of both versions. If either version does not have a value at that index, we consider that value to be zero.

Here is the detailed code for the solution:

def compareVersion(version1: str, version2: str) -> int:

# Split the versions into a list of integers
v1 = list(map(int, version1.split('.')))
v2 = list(map(int, version2.split('.')))

# Make the list lengths equal by padding with zeros where necessary
if len(v1) > len(v2):
    v2 += [0] * (len(v1) - len(v2))
elif len(v1) < len(v2):
    v1 += [0] * (len(v2) - len(v1))

# Compare each revision of the versions
for i in range(len(v1)):
    if v1[i] < v2[i]:
        return -1
    elif v1[i] > v2[i]:
        return 1

# If all revisions are equal, return 0
return 0

The time complexity of this solution is O(n), where n is the length of the longer version string. This is because we split both versions into lists of integers and then compare each item of the two lists, which takes O(n) time. The space complexity is also O(n), as we create lists to store the integer values of the versions.

1