O(n + m) O(n + m)
Intuition
Split each version into revision numbers and compare them position by position as integers, padding the shorter one with zeros.
Explanation
Compare revisions numerically
Split both versions on . into lists of revisions. Compare index by index as integers (so 01 == 1), treating a missing revision as 0. Return -1/1 at the first difference, else 0.
a, b = v1.split('.'), v2.split('.')
for i in range(max(len(a), len(b))):
x = int(a[i]) if i<len(a) else 0
y = int(b[i]) if i<len(b) else 0
if x != y: return -1 if x<y else 1
return 0
Worked example
"1.2" vs "1.10" → 1==1, then 2 < 10 → -1.
Complexity
- Time: O(n + m).
- Space: O(n + m).
Implementation
class Solution {
public int compareVersion(String version1, String version2) {
String[] a = version1.split("\\.");
String[] b = version2.split("\\.");
int m = Math.max(a.length, b.length);
for (int i = 0; i < m; i++) {
int x = i < a.length ? Integer.parseInt(a[i]) : 0;
int y = i < b.length ? Integer.parseInt(b[i]) : 0;
if (x < y) return -1;
if (x > y) return 1;
}
return 0;
}
}