algoadvance

Leetcode 165. Compare Version Numbers

Problem Statement

You are given two version numbers, version1 and version2, composed of one or more integers separated by a dot (.). Each version number consists of multiple sections separated by dots. Each section within the version numbers contains only digits.

For example, version1 = "1.0" and version2 = "1.0.0" are valid version numbers.

You need to compare these version numbers to find out which one is greater, or if they are equal. The possible outcomes are:

• Return 1 if version1 > version2
• Return -1 if version1 < version2
• Return 0 if version1 == version2

Note that:

• 1.0 is considered equal to 1.0.0 (trailing zeros can be ignored).
• The sections are compared as integers, so 1.0.0 is the same as 1.0.

Clarifying Questions

1. Input format:
   • Confirm if the inputs version1 and version2 are always valid version strings.
   • Are the version numbers always non-empty strings?
2. Constraints:
   • What is the maximum length of the version string?
   • Does the version string always contain only digits and dots, and are sections always non-empty?
3. Edge Cases:
   • How to handle leading zeros in a version section? For example, version1 = "1.01", version2 = "1.001".

Strategy

1. Split the Version Strings:
   • Split version1 and version2 by the dot . to get a list of integers indicating each section of the version numbers.
2. Normalize Section Lists:
   • Normalize the lists by appending zeros to the shorter list to make their lengths equal.
3. Comparison:
   • Compare the sections one by one as integers. The first non-equal section will determine the result.
4. Edge Handling:
   • If all corresponding sections are equal, then the versions are equal.

Code

Here is the C++ implementation for comparing version numbers:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

std::vector<int> splitVersion(const std::string& version) {
    std::vector<int> components;
    std::stringstream ss(version);
    std::string item;
    while (std::getline(ss, item, '.')) {
        components.push_back(std::stoi(item));
    }
    return components;
}

int compareVersion(std::string version1, std::string version2) {
    std::vector<int> v1 = splitVersion(version1);
    std::vector<int> v2 = splitVersion(version2);
    
    int length = std::max(v1.size(), v2.size());
    
    for (int i = 0; i < length; ++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;
}

// Example usage
int main() {
    std::string version1 = "1.01";
    std::string version2 = "1.001";
    
    std::cout << compareVersion(version1, version2) << std::endl;
    
    return 0;
}

Time Complexity

• Splitting Versions: Splitting the version string by . takes O(n) where n is the length of the longest string version.
• Comparison: The comparison iterates through the sections which takes O(m) where m is the number of sections (max length between both versions).

Overall, the time complexity of the function is O(n + m).

Feel free to ask for any further clarifications or optimizations!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?