Simple JAVA Solution


  • 25
    A
    public class Solution {
        public int compareVersion(String version1, String version2) {
            String[] v1 = version1.split("\\.");
            String[] v2 = version2.split("\\.");
            
            int longest = v1.length > v2.length? v1.length: v2.length;
            
            for(int i=0; i<longest; i++)
            {
                int ver1 = i<v1.length? Integer.parseInt(v1[i]): 0;
                int ver2 = i<v2.length? Integer.parseInt(v2[i]): 0;
                
                if(ver1> ver2) return 1;
                if(ver1 < ver2) return -1;
            }
            return 0;
        }
    }
    

    Any comments would be appreciated.
    Basically I split the string with regex "." (it was written "\." since "." only means any character), then using looping, I tried to find out the value of the version using parseInt.
    If one version has a lesser subversion than the others, it will be filled with zeros.

    for example: 1 vs 1.01 --> 1.00 vs 1.01

    it ran in about 230ms, any suggestion to make it faster with Java language?
    What can be optimized?


  • 0
    T

    What if the value of a subversion is larger than Integer. MAX_VALUE?


  • 0
    A

    I think that would be a very special case,, you remind me of Gangnam Style on Youtube lol.
    if it's larger than max integer, we should use long integer data type.


  • 0
    T

    For me, I will process the string directly, even the long integer data type has its MAX_VALUE, of course it is special, but it is possible.


  • 0
    C

    yeah. Deal with string directly would be better. Just string.compareTo(anotherString) will do


  • 0
    D

    If you deal with string directly, how can you handle situations like:
    001, 1? To string comparison, "1" is larger than "001" lexicographically, which would yield the result to be -1, but they are the same.


  • 0
    F

    you don't have to use "compareTo", just compare the string manually, it should be easy.


  • 0
    S

    Some guys point to MAX_VALUE problem, I think it is a good point. I revise my solution to solve this problem and without using compareTo().

    The basic idea is same.

    strCmp() method is used to compare two tokens without parsing to int. The idea of this method is very very similar: fill zeros if the length is not consistent.

    for example: "001" vs. "1" --> "001" vs. "001"

    public class Solution {
        public int compareVersion(String version1, String version2) {
            String ver1[] = version1.split("\\.");
            String ver2[] = version2.split("\\.");
            
            int len = ver1.length > ver2.length ? ver1.length : ver2.length;
            
            for (int i = 0; i < len; i++)
            {
                String v1 = i < ver1.length ? ver1[i] : "0";
                String v2 = i < ver2.length ? ver2[i] : "0";
                
                int compare = strCmp(v1, v2);
                if (compare != 0) return compare;
            }
            return 0;
        }
        
        public int strCmp(String s1, String s2)
        {
            int len = s1.length() > s2.length() ? s1.length() : s2.length();
            for (int i = 0; i < len; i++)
            {
                char v1 = i + s1.length() < len ? '0' : s1.charAt(i - len + s1.length());
                char v2 = i + s2.length() < len ? '0' : s2.charAt(i - len + s2.length());
                if (v1 > v2) return 1;
                if (v1 < v2) return -1;
            }
            return 0;
        }
    }
    

  • 0
    Y

    Nice solution. Thanks. Could any one tell me the time complexity?

    My understanding is:

    1. split: O(n), n is the length of the longer string array.
    2. loop: O(kn), k is the average length of subversion number
      I check the Integer.parseInt source code, it should be O(k).

    So the result will be O(kn)? Am I right? Thanks.


  • 0
    A

    @ynys why do you take average length? In my opinion it is O(n^2)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.