My AC solution and some clarifications about the inputs


  • 1
    Z

    As an interview question, we can ask the interviewer about the possible inputs. Such as, how many dots the string can have, zero or more? Is the version number within the range of a 32 bit integer? Are there some leading or tailing zeros in the string.

    For this LeetCode question, the input can be like this: 001.3.3.7.000 and 1.3.3.7. The expected answer for this two version is equal.

    To compare this kind of versions, we can tokenize the strings with the dot as delimiter and then compare the integer translation side by side, from the left to right the end of one string.

    public int compareVersion(String version1, String version2) {
        String[] list1 = version1.split("\\.");
        String[] list2 = version2.split("\\.");
        int i = 0;
        while ( i < list1.length && i < list2.length) {
            int a = Integer.valueOf(list1[i]);
            int b = Integer.valueOf(list2[i]);
            if (a < b)
                return -1;
            else if (a > b)
                return 1;
            else
                i++;
        }
        // All list1[i] == list2[i], then i reach the end of list1 or list2
        if (list1.length == list2.length)
            return 0;
        // list2 is longer, check whether the remaining is zeros
        while (i < list2.length) {
            int b = Integer.valueOf(list2[i++]);
            if (b != 0)
                return -1;
        }
        while (i < list1.length) {
            int a = Integer.valueOf(list1[i++]);
            if (a != 0)
                return 1;
        }
        return 0;        
    }

  • 4
    F

    We can make it more concise by add zeros to list. And it would be better to do input validation first.

    public static int compareVersion(String version1, String version2) {
        if (version1 == null && version2 == null) return 0;
        if (version1 == null || version2 == null) return version1 == null ? -1 : 1;
        String[] list1 = version1.split("\\.");
        String[] list2 = version2.split("\\.");
        int i = 0;
        while (i < list1.length || i < list2.length) {
            int a = i < list1.length ? Integer.valueOf(list1[i]) : 0;
            int b = i < list2.length ? Integer.valueOf(list2[i]) : 0;
            if (a < b) return -1;
            else if (a > b) return 1;
            i++;
        }
        return 0;
    }

  • 0
    Z

    That's a cool idea! Thanks for your sharing!


Log in to reply
 

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