Problem Description

The "Compare Version Numbers" problem asks you to compare two version numbers given as strings, version1 and version2. Each version string consists of one or more non-negative integers separated by dots ('.'). For example, "1.0.1" or "2.3". You need to determine which version is greater, or if they are equal.

• If version1 is greater than version2, return 1.
• If version1 is less than version2, return -1.
• If both are equal, return 0.

Key constraints:

• Leading zeros in each revision number are allowed and should be ignored (e.g., "01" == "1").
• If a version string is shorter, missing revisions are treated as 0 (e.g., "1.0" == "1.0.0").
• All revision numbers are non-negative integers.

Thought Process

At first glance, comparing two version numbers seems straightforward, but the presence of multiple revisions (separated by dots), leading zeros, and different lengths complicate things.

A brute-force approach might be to split both strings by the dot, convert each revision to an integer, and compare them one by one. If one version has more revisions, treat the missing ones as zeros. This avoids issues with leading zeros and different lengths.

Optimizing further, we realize we only need to compare corresponding revisions until we find a difference; we can stop early. If no difference is found, the versions are equal.

Solution Approach

To solve the problem efficiently, we follow these steps:

1. Split both version strings into a list of revision numbers using the dot '.' as a delimiter.
2. Iterate through the revisions in parallel. If one list is shorter, treat the missing values as 0.
3. Convert each revision to an integer. This automatically ignores leading zeros.
4. Compare the corresponding revisions:
   • If a revision in version1 is greater, return 1.
   • If a revision in version2 is greater, return -1.
   • If they are equal, continue to the next revision.
5. If all revisions are equal (including any trailing zeros), return 0.

This approach is efficient and handles all edge cases, such as different numbers of revisions and leading zeros.

Example Walkthrough

Let's walk through an example with version1 = "1.01" and version2 = "1.001.0".

1. Split both versions:
   • version1: ["1", "01"]
   • version2: ["1", "001", "0"]
2. Pad the shorter version with zeros:
   • version1: ["1", "01", "0"]
   • version2: ["1", "001", "0"]
3. Compare each revision (after converting to integers):
   • First: 1 vs 1 → equal
   • Second: 1 vs 1 (since "01" and "001" both become 1) → equal
   • Third: 0 vs 0 → equal
4. All revisions are equal, so return 0.

Time and Space Complexity

Brute-force Approach:

• Splitting the strings and comparing each revision: O(N + M), where N and M are the lengths of the two version strings.
• Space: O(N + M) to store the split revisions.

• We still need to process every character at least once, so time complexity remains O(N + M).
• Space complexity is also O(N + M) for the revision arrays.

No significant improvement is possible since we must examine each revision.

Code Implementation

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = version1.split('.')
        v2 = version2.split('.')
        max_len = max(len(v1), len(v2))
        for i in range(max_len):
            num1 = int(v1[i]) if i < len(v1) else 0
            num2 = int(v2[i]) if i < len(v2) else 0
            if num1 > num2:
                return 1
            elif num1 < num2:
                return -1
        return 0
    

class Solution {
public:
    int compareVersion(string version1, string version2) {
        vector<int> v1, v2;
        split(version1, v1);
        split(version2, v2);
        int n = max(v1.size(), v2.size());
        for (int i = 0; i < n; ++i) {
            int num1 = i < v1.size() ? v1[i] : 0;
            int num2 = i < v2.size() ? v2[i] : 0;
            if (num1 > num2) return 1;
            if (num1 < num2) return -1;
        }
        return 0;
    }
private:
    void split(const string& version, vector<int>& out) {
        int n = version.size(), i = 0;
        while (i < n) {
            int num = 0;
            while (i < n && version[i] != '.') {
                num = num * 10 + (version[i] - '0');
                ++i;
            }
            out.push_back(num);
            ++i;
        }
    }
};
    

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\\\.");
        String[] v2 = version2.split("\\\\.");
        int n = Math.max(v1.length, v2.length);
        for (int i = 0; i < n; i++) {
            int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;
            if (num1 > num2) return 1;
            if (num1 < num2) return -1;
        }
        return 0;
    }
}
    

var compareVersion = function(version1, version2) {
    let v1 = version1.split('.');
    let v2 = version2.split('.');
    let n = Math.max(v1.length, v2.length);
    for (let i = 0; i < n; i++) {
        let num1 = i < v1.length ? parseInt(v1[i], 10) : 0;
        let num2 = i < v2.length ? parseInt(v2[i], 10) : 0;
        if (num1 > num2) return 1;
        if (num1 < num2) return -1;
    }
    return 0;
};
    

Summary

The "Compare Version Numbers" problem is a classic string manipulation and comparison task. By splitting the version strings, converting revisions to integers, and aligning their lengths, we can efficiently compare them revision by revision. This approach handles all edge cases, such as leading zeros and different numbers of revisions, and has optimal time and space complexity for the problem. The solution is both simple and robust, making it a great example of careful string processing and incremental comparison.