Given two version strings version1 and version2 containing dot-separated non-negative integers. Compare revisions from left to right by ignoring leading zeroes and treating each missing revision as 0. Return -1 when version1 is smaller, 1 when it is larger, and 0 when their values are equal.
A revision is one group of digits. A version with no dots has one revision.
Example 1
Input: version1 = "01.002.000.00120.9", version2 = "1.2.0.119.99"
Output: 1
Explanation: The first three revision pairs have values 1, 2, and 0 on both sides. The fourth revision is 120 in version1 and 119 in version2. That pair makes version1 larger.
Example 2
Input: version1 = "7", version2 = "007.00.0"
Output: 0
Explanation: The first revisions both have value 7. Each of the two remaining zero revisions in version2 matches an implied zero in version1.
Approach
Splitting each version at its dots gives two lists of revisions. Entries at the same position belong to the same comparison. The first unequal pair decides the version order because revisions further to the right have lower priority. A missing revision counts as zero.
Leading zeroes add nothing to a revision's value. Once they are removed, the revision with more digits has a nonzero digit in a higher decimal place, so its value is larger. If the revision from version1 has fewer remaining digits, return -1. If it has more, return 1. An all-zero or missing revision has no remaining digits, so either compares as zero.
If the digit counts match, both revisions use the same decimal places. The first differing digit from the left has enough place value to outweigh every digit to its right. Return -1 if that digit is smaller in version1, or 1 if it is larger. If the digits match, the revisions are equal and the next pair can decide the order. Return 0 if every pair matches.
Algorithm
Split each version at dots to build its revision list. Compare entries at the same position from left to right through the end of the longer list. A version without dots contributes one revision.
Remove leading zeroes from each revision because they add nothing to its value. Represent an all-zero or missing revision with an empty digit string so both compare as zero.
If the current revision from
version1has fewer remaining digits than the revision fromversion2, return-1. With leading zeroes removed, fewer digits mean a smaller value.If the current revision from
version1has more remaining digits than the revision fromversion2, return1. Its extra decimal place makes its value larger.If the digit counts are equal, compare digits from left to right. At the first difference, return
-1if the digit fromversion1is smaller or1if it is larger. That decimal place outweighs every digit to its right.If all digits in the pair match, continue to the next revision because a later pair may still differ. Return
0only after every pair matches, including the implied zeroes for missing revisions.
Dry Run
Compare Version Numbers
Solution
#include <bits/stdc++.h>using namespace std;class Solution { // Returns the dot-separated revisions. vector<string> splitRevisions(const string& version) { vector<string> revisions; stringstream stream(version); string revision; // Read one revision per dot and store it in order. while (getline(stream, revision, '.')) { revisions.push_back(revision); } return revisions; } // Returns the digits after the leading zeroes. string significantDigits(const string& revision) { size_t start = 0; // An all-zero revision leaves an empty string. while (start < revision.size() && revision[start] == '0') { ++start; } return revision.substr(start); }public: // Returns the comparison result for the two versions. int compareVersion(const string& version1, const string& version2) { vector<string> revisions1 = splitRevisions(version1); vector<string> revisions2 = splitRevisions(version2); size_t count = max(revisions1.size(), revisions2.size()); // Visit every revision position, including any unpaired suffix. for (size_t index = 0; index < count; ++index) { // An exhausted list contributes zero, represented by an empty string. string first = index < revisions1.size() ? significantDigits(revisions1[index]) : ""; string second = index < revisions2.size() ? significantDigits(revisions2[index]) : ""; // The revision with more significant digits is larger. if (first.size() != second.size()) { return first.size() < second.size() ? -1 : 1; } // For equal lengths, digit order decides the first unequal pair. if (first != second) { return first < second ? -1 : 1; } } return 0; }};// Driver codeint main() { string version1 = "01.002.000.00120.9"; string version2 = "1.2.0.119.99"; // instance for class Solution Solution sol; cout << sol.compareVersion(version1, version2) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(M + N) in the worst case because splitting and comparing the revisions take linear work in the input lengths.
Space Complexity: O(M + N) auxiliary space for the split lists and the temporary digit strings.
Interview follow-up Questions
Alphabetical order puts "1.10" before "1.2" because 1 comes before 2 at the first differing character. The second revisions have numeric values 10 and 2, so "1.10" is the larger version.
Be the first to add a comment.