Leetcode 165. Compare Version Numbers

Problem Explanation

We need to compare two version numbers which are represented as strings. Each number string is separated by '.'.

If version1 > version2 we need to return 1, if version1 < version2 return -1 else return 0.

Note that the '.' dot doesn't represent a decimal point, but a separator between different levels of version numbers. Also, we ignore leading zeroes. If a version number doesn't specify a level revision number, it default to "0".

Below let's walk through the problem with one of the given examples:

version1 = "1.0.1", version2 = "1"

Start reading from the left of both version numbers, when we encounter the first '.', we have 1 and 1 for version1 and version2 respectively, so we move on to the next number. For version1, after the first '.', we have '0', but version2 doesn't have a numberย after first '.', so we default it to '0'. Now, after the second '.', version1 has '1', but version2 doesn't have a number after the second '.', so we default it to '0'. Here, since '1' > '0', we say version1 > version2, thus we return 1.

Solution Approach The solution uses a simple approach of string parsing and comparison using integer values. We use an istringstream object to read integer values with respect to '.'. We read the integer values before each '.' from the istringstream object for a version number and then compare it with the corresponding integer value from the other version number. If the integer values are equal, we continue to the next '.' in the string, else, we can make a decision if version1 > version2 or version1 < version2.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int compareVersion(string version1, string version2) {
6        istringstream iss1(version1);
7        istringstream iss2(version2);
8        int v1;
9        int v2;
10        char dotChar;
11
12        while (bool(iss1 >> v1) + bool(iss2 >> v2)) {
13            if (v1 < v2)
14                return -1;
15            if (v1 > v2)
16                return 1;
17            iss1 >> dotChar;
18            iss2 >> dotChar;
19            v1 = 0;
20            v2 = 0;
21        }
22
23        return 0;
24    }
25};

Python Solution

1
2python
3class Solution(object):
4    def compareVersion(self, version1, version2):
5        versions1 = [int(v) for v in version1.split(".")]
6        versions2 = [int(v) for v in version2.split(".")]
7        for i in range(max(len(versions1),len(versions2))):
8            v1 = versions1[i] if i<len(versions1) else 0
9            v2 = versions2[i] if i<len(versions2) else 0
10            if v1>v2:
11                return 1
12            elif v1<v2:
13                return -1;
14        return 0

Java Solution

1
2java
3public class Solution {
4    public int compareVersion(String version1, String version2) {
5        String[] nums1 = version1.split("\\.");
6        String[] nums2 = version2.split("\\.");
7        int n1 = nums1.length, n2 = nums2.length;
8        
9        for (int i = 0; i < Math.max(n1, n2); i++) {
10            int i1 = i < n1 ? Integer.parseInt(nums1[i]) : 0;
11            int i2 = i < n2 ? Integer.parseInt(nums2[i]) : 0;
12            if (i1 < i2) {
13                return -1;
14            } else if (i1 > i2) {
15                return 1;
16            }
17        }
18        return 0;
19    }
20}

JavaScript Solution

1
2javascript
3var compareVersion = function(version1, version2) {
4    let arr1 = version1.split(".");
5    let arr2 = version2.split(".");
6    
7    let length = Math.max(arr1.length, arr2.length);
8
9    for(let i=0; i<length; i++){
10        let v1 = arr1[i] === undefined ? 0 : parseInt(arr1[i]);
11        let v2 = arr2[i] === undefined ? 0 : parseInt(arr2[i]);
12        
13        if(v1 > v2){
14            return 1;
15        } else if(v1 < v2){
16            return -1;
17        }
18    }
19
20    return 0;
21};

C# Solution

1
2csharp
3public class Solution {
4    public int CompareVersion(string version1, string version2) {
5        string[] v1 = version1.Split('.');
6        string[] v2 = version2.Split('.');
7        int i = 0;
8        while (i < v1.Length || i < v2.Length) {
9            int num1 = i < v1.Length ? int.Parse(v1[i]) : 0;
10            int num2 = i < v2.Length ? int.Parse(v2[i]) : 0;
11            if (num1 < num2) {
12                return -1;
13            } else if (num1 > num2) {
14                return 1;
15            }
16            i++;
17        }
18        return 0;
19    }
20}

In all these solutions, the key point is the enumeration of the split strings or the integer lists. For each character or integer, we're comparing them one by one until we find a point where one version is greater than the other or till the end.

The '0' padding in the case of uneven versions helps us to not stumble upon incomplete iterations. In python, we handle this explicitly in a loop by providing a conditional statement to take 0 if the index exceeds the version length. A similar approach is used in JavaScript.

In Java, we predetermined the maximum length of both the versions and ran our loop till that value. In this loop, if the index is larger than the size of the version string, the value is set to 0.

In C#, we perform comparisons by iterating over the split versions' length. If the index exceeds the length of the version string, we assign the value as 0.

The C++ solution uses a different approach by using an istringstream object and character dotChar as a delimiter to read version hank at each step.

As we can see, the methodology remains the same across languages - split the versions, convert the hanks into integers, compare at each level. However, the implementation may differ slightly depending on the string manipulation and data processing features available in each language.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ