Last active
April 1, 2024 12:27
-
-
Save dluciano/5ad4018457b8e2d7ac3c3fd46f4ac159 to your computer and use it in GitHub Desktop.
Compare version of n parts
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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++; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
165. Compare Version Numbers