String number compare, O(m+n)
when compare revision , first delete beginning 0s, then if length not equal, longer one is larger.
class Solution {
public int compareVersion(String version1, String version2) {
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
int m = v1.length;
int n = v2.length;
int i = 0;
// System.out.println(version1);
// System.out.println(Arrays.toString(v1));
for (;i<Math.min(m,n);i++){
int flag = compare(v1[i], v2[i]);
System.out.println(flag);
if (flag != 0) return flag;
}
while (i<m) {
int flag = compare(v1[i], "0");
if (flag != 0) return flag;
i++;
}
while (i<n) {
int flag = compare("0", v2[i]);
if (flag != 0) return flag;
i++;
}
return 0;
}
public int compare(String revision1, String revision2){
int i = 0, j=0;
int m = revision1.length(), n = revision2.length();
while (i<m && revision1.charAt(i) == '0') i++;
while (j<n && revision2.charAt(j) == '0') j++;
// longer number is larger
if (m-i>n-j) return 1;
else if (m-i<n-j) return -1;
while (i<m && j<n) {
if (revision1.charAt(i) < revision2.charAt(j)) return -1;
else if (revision1.charAt(i)>revision2.charAt(j)) return 1;
i++;
j++;
}
if (i<m) return 1;
else if (j<n) return -1;
else return 0;
}
}