
Description
The problem is to compare two version numbers, version1
and version2
, which are given as strings. Each version string consists of several levels separated by dots (e.g., "1.0.1"). Each level in the version is an integer that might contain leading zeros. The task is to determine which version is greater, or if they are equal, by comparing the integers at each corresponding level.
The possible outcomes are:
- Return
1
ifversion1
is greater thanversion2
. - Return
-1
ifversion1
is less thanversion2
. - Return
0
if both versions are equal.
Intuition
To compare the versions, we can break each version string into its individual levels, compare the corresponding levels one by one, and determine which version is greater based on the first non-equal level. If all levels are equal, then the versions are equal. By treating each level as an integer, we can avoid complications due to leading zeros.
Approach
- Helper Function:
- Create a helper function to parse and return the integer value of a level starting from a given index in the version string, stopping when a dot
.
or the end of the string is encountered. - Iterate Through Both Versions:
- Initialize two pointers
i
andj
to traverse throughversion1
andversion2
. - Use the helper function to extract and compare each level fromversion1
andversion2
. - If the current level fromversion1
is greater than that fromversion2
, return1
. - If the current level fromversion1
is less than that fromversion2
, return-1
. - Move the pointers to the next level and repeat. - Return Result:
- If all levels are equal after the loop, return
0
to indicate that the versions are equal.
Complexity
Time Complexity:
O(n + m)
, where n
is the length of version1
and m
is the length of version2
. Each character in both version strings is processed once.
Space Complexity:
O(1)
. The algorithm uses a constant amount of extra space, aside from the input strings.
Code
C++
class Solution {
public:
int compareVersion(string version1, string version2) {
auto helper = [](const string& s, int& idx) {
int num = 0;
while (idx < s.size()) {
if (s[idx] == '.') break;
else num = num * 10 + (s[idx] - '0');
idx++;
}
return num;
};
int i = 0, j = 0;
while (i < version1.size() || j < version2.size()) {
int v1 = (i < version1.size()) ? helper(version1, i) : 0;
int v2 = (j < version2.size()) ? helper(version2, j) : 0;
if (v1 > v2) return 1;
else if (v1 < v2) return -1;
i++;
j++;
}
return 0;
}
};
Python
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
def helper(s: str, idx: int) -> (int, int):
num = 0
while idx < len(s):
if s[idx] == '.':
break
else:
num = num * 10 + int(s[idx])
idx += 1
return num, idx + 1
i, j = 0, 0
while i < len(version1) or j < len(version2):
v1, i = helper(version1, i)
v2, j = helper(version2, j)
if v1 > v2:
return 1
elif v1 < v2:
return -1
return 0
Java
class Solution {
public int compareVersion(String version1, String version2) {
int i = 0, j = 0;
while (i < version1.length() || j < version2.length()) {
int v1 = 0, v2 = 0;
while (i < version1.length() && version1.charAt(i) != '.') {
v1 = v1 * 10 + (version1.charAt(i) - '0');
i++;
}
while (j < version2.length() && version2.charAt(j) != '.') {
v2 = v2 * 10 + (version2.charAt(j) - '0');
j++;
}
if (v1 > v2) return 1;
else if (v1 < v2) return -1;
i++;
j++;
}
return 0;
}
}
JavaScript
var compareVersion = function(version1, version2) {
const helper = function(s, idx) {
let num = 0;
while (idx < s.length) {
if (s[idx] === '.') break;
else num = num * 10 + parseInt(s[idx]);
idx++;
}
return [num, idx + 1];
};
let i = 0, j = 0;
while (i < version1.length || j < version2.length) {
const [v1, next1] = helper(version1, i);
const [v2, next2] = helper(version2, j);
if (v1 > v2) return 1;
else if (v1 < v2) return -1;
i = next1;
j = next2;
}
return 0;
};