How to Compare Version Numbers in C++?

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

This C++ coding exercise helps you review the STL::vector, string.substr and how to convert string type to integer.

Convert String to Integer

In C++ 11, you can use std::stoi(s) function to convert string to integer instead of using the C-style atoi(s.c_str())

Split String by Delimiter

Given a delimiter character, the following function splits the string and push the sub-strings into a vector.

1
2
3
4
5
6
7
8
9
10
11
12

vector<string> split(const string& s, char d) {
    vector<string> r;
    int j = 0;
    for (int i = 0; i < s.length(); i ++) {
        if (s[i] == d) {
            r.push_back(s.substr(j, i - j));
            j = i + 1;
        }
    }
    r.push_back(s.substr(j));
    return r;
}

vector<string> split(const string& s, char d) {
    vector<string> r;
    int j = 0;
    for (int i = 0; i < s.length(); i ++) {
        if (s[i] == d) {
            r.push_back(s.substr(j, i - j));
            j = i + 1;
        }
    }
    r.push_back(s.substr(j));
    return r;
}

The Solution

With the above knowledge, it is easy to come up with a straightforward solution. The idea is to split both version strings into vector of string. Pad the ‘0’ to the shorter version string, so both vector of string are the same size and compare both vector one by one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int compareVersion(string version1, string version2) {
    auto v1 = split(version1, '.');
    auto v2 = split(version2, '.');
    int max = v1.size() > v2.size() ? v1.size() : v2.size();
    // pad the shorter version string
    if (v1.size() != max) {
        for (int i = max - v1.size(); i --; ) {
            v1.push_back("0");
        }
    } else {
        for (int i = max - v2.size(); i --; ) {
            v2.push_back("0");
        }
    }
    for (int i = 0; i < max; i ++) {
        int n1 = stoi(v1[i]);
        int n2 = stoi(v2[i]);
        if (n1 > n2) {
            return 1;
        } else if (n1 < n2) {
            return -1;
        }
    }
    return 0;
}

int compareVersion(string version1, string version2) {
    auto v1 = split(version1, '.');
    auto v2 = split(version2, '.');
    int max = v1.size() > v2.size() ? v1.size() : v2.size();
    // pad the shorter version string
    if (v1.size() != max) {
        for (int i = max - v1.size(); i --; ) {
            v1.push_back("0");
        }
    } else {
        for (int i = max - v2.size(); i --; ) {
            v2.push_back("0");
        }
    }
    for (int i = 0; i < max; i ++) {
        int n1 = stoi(v1[i]);
        int n2 = stoi(v2[i]);
        if (n1 > n2) {
            return 1;
        } else if (n1 < n2) {
            return -1;
        }
    }
    return 0;
}

The overall time complexity is O(N) where N is the maximum sub-version number and the space complexity is O(N) as well.

–EOF (The Ultimate Computing & Technology Blog) —