Skip to content

Instantly share code, notes, and snippets.

@dluciano
Last active April 1, 2024 12:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dluciano/5ad4018457b8e2d7ac3c3fd46f4ac159 to your computer and use it in GitHub Desktop.
Save dluciano/5ad4018457b8e2d7ac3c3fd46f4ac159 to your computer and use it in GitHub Desktop.
Compare version of n parts
public class Solution {
public int CompareVersion(string version1, string version2) {
return Compare(version1, version2);
}
public int Compare(string versionA, string versionB)
{
// Null checks added for completeness
if (versionA is null && versionB is null) return 0;
if (versionA is null) return -1;
if (versionB is null) return 1;
int ai = 0, bi = 0;
while (ai < versionA.Length && bi < versionB.Length)
{
// Skip leading zeros
while (ai < versionA.Length && versionA[ai] == '0' && versionA[ai] != '.')
ai++;
while (bi < versionB.Length && versionB[bi] == '0' && versionB[bi] != '.')
bi++;
// (Condition A): Finish the loop if the version only contains zeros for the current part of versionA and/or versionB
if (ai == versionA.Length && bi == versionB.Length || (ai == versionA.Length || bi == versionB.Length))
break;
// Skip the current version part because versionA and versionB contain only zeros
if (versionA[ai] == '.' && versionB[bi] == '.')
{
NextPart();
continue;
}
// Note: from now on, either versionA or versionB has a non-zero value because all leading zero edge cases were discarded.
// versionA only contains zero because we reached the dot for its current version part, thus versionB must have a non-zero value and versionA is less than versionB
if (versionA[ai] == '.') return -1;
// versionB only contains zero because we reached the dot for its current version part, thus versionA must have a non-zero value and versionA is greater than versionB
if (versionB[bi] == '.') return 1;
// Use the bias to temporarily store the smaller/greater version. We need the bias for cases like 1.1 and 1.10, where both versions have different lengths, and the algorithm would check 1.1 and 1.1 (the zero of versionB won't be checked because we reach the end of the part of versionA) are equals, however, we need to check if there are any other values left in versionA or versionB that would change our decision
var bias = int.MinValue;
while (
ai < versionA.Length &&
bi < versionB.Length &&
versionA[ai] != '.' &&
versionB[bi] != '.' &&
bias == int.MinValue)
{
if (versionA[ai] < versionB[bi])
bias = -1;
else if (versionA[ai] > versionB[bi])
bias = 1;
++ai;
++bi;
}
// Check if versionA has any other numeral (0-9), if so, versionA is greater
if(ai < versionA.Length && versionA[ai] != '.' && (bi >= versionB.Length || versionB[bi] == '.'))
return 1;
// Check if versionA has any other numeral (0-9), if so, versionA is smaller
if(bi < versionB.Length && versionB[bi] != '.' && (ai >= versionA.Length || versionA[ai] == '.'))
return -1;
// If the bias is -1 or 1, then return its value
if(bias != int.MinValue) return bias;
// Otherwise, both version parts are equal
NextPart();
}
// When both versions are equal, like 1.0.0 and 1.0, we return 0. However, we need to check if either version has any valid numeral different from 0. For instance: 1.0.1 and 1.0, in that case, this algorithm would break because of condition (A), but we still need to check if none of the versions have any other non-zero numeral.
while(ai < versionA.Length)
{
if(versionA[ai] != '.' && versionA[ai] != '0')
return 1;
ai++;
}
while(bi < versionB.Length)
{
if(versionB[bi] != '.' && versionB[bi] != '0')
return -1;
bi++;
}
return 0;
void NextPart()
{
if (ai < versionA.Length && versionA[ai] == '.')
ai++;
if (bi < versionB.Length && versionB[bi] == '.')
bi++;
}
}
}
@dluciano
Copy link
Author

dluciano commented Apr 1, 2024

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment