Compare Version Numbers
Medium · Two Pointers · Explanation and code example
Compare Numeric Revisions
How it works
Split or stream each version into numeric revisions. Compare matching revisions from left to right, interpreting a missing revision as zero. Converting each revision to an integer removes leading zeros without changing its numeric value.
Steps
- Read the next revision from each version.
- Compare them numerically, substituting zero when one version ends.
- Return zero when all revisions match.
Complexity
- Time: O(n + m) for the two input lengths.
- Space: Python O(n + m) for split revisions; C++ O(n + m) for stream copies.
Things to watch for
- Compare numeric values rather than strings;
10exceeds2. 1.0and1are equal.- Leading zeros do not create a different revision.
Python code example
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
levels1 = version1.split('.')
levels2 = version2.split('.')
length = max(len(levels1), len(levels2))
for i in range(length):
v1 = int(levels1[i]) if i < len(levels1) else 0
v2 = int(levels2[i]) if i < len(levels2) else 0
if v1 < v2:
return -1
if v1 > v2:
return 1
return 0
C++ code example
class Solution {
public:
int compareVersion(string version1, string version2) {
istringstream iss1(version1);
istringstream iss2(version2);
int v1 = 0;
int v2 = 0;
char dotChar;
while (bool(iss1 >> v1) + bool(iss2 >> v2)) {
if (v1 < v2)
return -1;
if (v1 > v2)
return 1;
iss1 >> dotChar;
iss2 >> dotChar;
v1 = 0;
v2 = 0;
}
return 0;
};
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.