Comparing Version Numbers in C++ using String Parsing

Version numbers are commonly used to indicate the progression or updates of software or any other product. When working with version numbers in C++, it can be helpful to compare two versions to determine their relative order. This article presents a C++ solution that compares two version numbers using string parsing. The code provided demonstrates an efficient approach to compare version numbers and returns -1, 0, or 1 based on their relationship.

Let’s examine a problem from LeetCode along with its solution to gain a better understanding of it. To solve this problem, you can visit the corresponding LeetCode page by clicking on the following link: LeetCode Problem Link. Additionally, you can verify the correctness of the solution as explained in the provided link.

The task is to compare two version numbers, version1 and version2. Version numbers are composed of one or more revisions separated by dots. Each revision consists of digits and may contain leading zeros. Revisions are indexed from left to right, starting with index 0 for the leftmost revision. To compare version numbers, we compare their revisions from left to right. When comparing revisions, we ignore any leading zeros. If a version number does not specify a revision at a particular index, we consider it as 0. For example, the version number 1.0 is considered less than 1.1 because the first revision is the same (1), but the second revision is 0 for 1.0 and 1 for 1.1, and 0 is less than 1.

The frequency of this technical interview question being asked varies among different companies, with Amazon having asked it 7 times, Microsoft 4 times, Arista Networks 2 times, and Nutanix 2 times.

Solution

Let’s analyze the code step by step:

A. Function Signature:
The function takes two input strings version1 and version2, representing two version numbers, and returns an integer representing their relative order.

int compareVersion(string version1, string version2)

B. Initialization:
We initialize two pointers, i and j, to track the current position in the respective version strings. We also store the lengths of the version strings in n1 and n2 variables.

int i = 0, j = 0, n1 = version1.size(), n2 = version2.size();

C. String Parsing:
The code enters a loop that continues until both pointers reach the end of their respective version strings. It performs string parsing to extract numbers separated by dots (‘.’). Two nested while loops are used to parse each number. The inner while loop increments i or j and calculates the numerical value of the current number by multiplying the previous value by 10 and adding the digit value obtained from subtracting the character ‘0’.

while (i < n1 || j < n2) {
    int num1 = 0, num2 = 0;
    while (i < n1 && version1[i] != '.')
        num1 = num1 * 10 + (version1[i++] - '0');
    while (j < n2 && version2[j] != '.')
        num2 = num2 * 10 + (version2[j++] - '0');

D. Comparison:
After parsing a number from both versions, we compare num1 and num2 to determine their relative order. If num1 is greater than num2, it means version1 is greater, so we return 1. If num1 is smaller than num2, it means version1 is smaller, so we return -1.

if (num1 > num2)
    return 1;
else if (num1 < num2)
    return -1;

E. Incrementing Pointers:
After parsing a number, we increment both pointers i and j to skip the dot (‘.’) character and move to the next number in each version string.

i++;
j++;

F. Return:
If the code reaches this point, it means both version strings have been traversed completely, and all corresponding numbers were equal. Therefore, we return 0 to indicate that both versions are equal.

return 0;

Conclusion

In conclusion, version number tracking is critical in software development, and comparing version numbers can be a complex task. However, this article offers a practical solution in C++ that provides an efficient way to compare version numbers using string parsing. The code provided is straightforward and accompanied by a detailed explanation, making it easy for readers to comprehend and apply in their own projects. By implementing this solution, developers can simplify their version number comparison processes and improve their software development workflows.