If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
Idea: Brute force. First locate the first occurrence of '.' in the two strings, e.g.t denoted as dot1, dot2. Then split the strings to two halves at dot1 and dot2. Compare the first halves of the two strings, if they are not equal, return the result. Otherwise continue to compare the substrings after dot1 or dot2. If a string becomes empty, keep set its value to 0, since "1.0 == 1" in this problem's setting.
Time: O(n) Space: O(n) (in worst case, the substrings may be the whole string)
Code:
public class Solution {
public int compareVersion(String version1, String version2) {
String s1=version1;
String s2=version2;
while(s1.length()!=0||s2.length()!=0)
{
int dot1=s1.indexOf(".");
int dot2=s2.indexOf(".");
String sub11=(dot1==-1)?s1:s1.substring(0,dot1);
String sub21=(dot2==-1)?s2:s2.substring(0,dot2);
int v1=(sub11.length()==0)?0:Integer.parseInt(sub11);
int v2=(sub21.length()==0)?0:Integer.parseInt(sub21);
if(v1>v2)
return 1;
if(v1<v2)
return -1;
s1=(dot1==-1||dot1+1>=s1.length())?"":s1.substring(dot1+1,s1.length());
s2=(dot2==-1||dot2+1>=s2.length())?"":s2.substring(dot2+1,s2.length());
}
return 0;
}
}
No comments:
Post a Comment