Dare2Solve
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:
1
if version1
is greater than version2
.-1
if version1
is less than version2
.0
if both versions are equal.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.
Helper Function:
.
or the end of the string is encountered.Iterate Through Both Versions:
i
and j
to traverse through version1
and version2
.version1
and version2
.version1
is greater than that from version2
, return 1
.version1
is less than that from version2
, return -1
.Return Result:
0
to indicate that the versions are equal.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.
O(1)
. The algorithm uses a constant amount of extra space, aside from the input strings.
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;
}
};
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
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;
}
}
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;
};