Compare version numbers

Dec 18, 2024 • 4 mins read

Problem Overview

LeetCode Question: Compare Version Numbers

The problem is a classic problem based on string manipulation. It asks you to compare two version numbers given as strings and determine which one is greater, or if both are equal.

The comparison should be based on major, minor, patch, and other subsequent integer levels after splitting by the dot . character.

Problem Statement

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

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

Example

Example 1:
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represents the same integer "1".

Example 2:
Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 determined to be equal to version2 as 1.0 is the same as 1.0.0

Example 3:
Input: version1 = "0.1", version2 = "1.1"
Output: -1

Understanding the Problem

To solve this problem, you need to parse the version numbers and compare them part by part. Each part separated by a dot is a non-negative integer, and leading zeros should be ignored.

Characteristic Properties:

Compare the parts iteratively from the most significant to the least significant.
If one version has more levels, append zeroes to its shorter counterpart for comparison.
Deduplicate unnecessary zero-prefixed numbers since they don’t affect the comparison outcome.

Key DSA Concepts and Theory

The problem extensively leverages the following concepts:

1. String Manipulation

Decomposing strings into elements using delimiters (such as . in this case) is a basic string operation. You can use string library functions available in various programming languages to achieve this efficiently.

2. Array and List Manipulation

After splitting the string, you end up handling arrays and lists that store individual version components. These must be compared iteratively which involves basic array/list operations.

3. Integer Comparison

Each version component, after conversion from string to integer, should be compared using simple arithmetic operations.

Solution Approach

To solve this, follow these steps:

Split the Strings:
- Split version1 and version2 by the . character.
- Convert each segment into an integer to easily handle leading zeros.
Iterative Comparison:
- Use a loop to compare each segment's value of both versions.
- If one is greater than the other, immediately return the respective comparison result.
- If you run out of segments in one version but not the other, treat missing segments as zero since they don't alter value importance.
Post Loop Judgement:
- If none proves to be greater by end of the loop, they are equal by definition.

Code Implementation

C++ Code

#include <vector>
#include <sstream>
using namespace std;

int compareVersion(string version1, string version2) {
    stringstream v1(version1);
    stringstream v2(version2);
    string s1, s2;

    while (getline(v1, s1, '.') || getline(v2, s2, '.')) {
        int num1 = s1.empty() ? 0 : stoi(s1);
        int num2 = s2.empty() ? 0 : stoi(s2);
        if (num1 > num2) return 1;
        if (num1 < num2) return -1;
        s1.clear();
        s2.clear();
    }
    
    return 0;
}

Java Code

public int compareVersion(String version1, String version2) {
    String[] nums1 = version1.split("\\.");
    String[] nums2 = version2.split("\\.");
    
    int n1 = nums1.length, n2 = nums2.length;
    int i1, i2;
    for (int i = 0; i < Math.max(n1, n2); ++i) {
        i1 = i < n1 ? Integer.parseInt(nums1[i]) : 0;
        i2 = i < n2 ? Integer.parseInt(nums2[i]) : 0;
        if (i1 != i2) {
            return i1 > i2 ? 1 : -1;
        }
    }
    return 0;
}

Time and Space Complexity Analysis

Time Complexity: O(n + m), where n and m are the number of characters in version1 and version2 respectively. This is due to the parsing operation which potentially traverses and processes each character.
Space Complexity: O(n + m) in Java, due to the use of additional space for splitting strings into parts; O(1) in C++ since it doesn’t store every part separately after use.

Common Mistakes to Avoid

Not handling leading zeros: Ensure all version parts are parsed as integers to automatically ignore leading zeros.
Incorrectly comparing when length mismatches: Ensure to either append zeros or handle the missing segments appropriately.

Additional Resources and References

Check the official LeetCode solution for alternative implementations and optimizations.
Explore GeeksforGeeks for general string comparison methods.

By using these insights and methodologies, you can tackle a variety of problems that require parsing and comparing complex string formats efficiently.