[leetcode #165] Compare Version Numbers

Problem
Given two version numbers, version1 and version2, compare them.
Version numbers consist of one or more revisions joined by a dot '.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example 2.5.33 and 0.1 are valid version numbers.
To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.
Return the following:

・ If version1 < version2, return -1.
・ If version1 > version2, return 1.
・ Otherwise, return 0.

Example 1:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 2:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

Example 3:

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

Constraints:

・ 1 <= version1.length, version2.length <= 500
・ version1 and version2 only contain digits and '.'.
・ version1 and version2 are valid version numbers.
・ All the given revisions in version1 and version2 can be stored in a 32-bit integer.

Idea
これは、指定されたバージョンの最新バージョンが何であるかを決定する問題です.
バージョンの各リビジョンは「.」です.分割:各リビジョンの親リビジョンがより大きい場合、バージョンは最新バージョンになります.
「.」のindexを見つけて、各リビジョンをintegerに変更し、比較します.リビジョンのstringをarrayとして作成し、arrayのelementを比較する方法があります.
substringで解凍する方法はもっと速いが,最後のリビジョンを処理するとコードの長さが増加する.
Time Complexity: O(n)
Space Complexity: O(1)
Solution
サブストリングで解いた答え.(コード汚れ)

class Solution {
    public int compareVersion(String version1, String version2) {
        int dotIndex1 = 0;
        int dotIndex2 = 0;
        
        while (true) {
            int index1 = version1.indexOf('.', dotIndex1);
            int index2 = version2.indexOf('.', dotIndex2);

            int val1 = 0;
            if (index1 != -1) {
                val1 = Integer.parseInt(version1.substring(dotIndex1, index1));
                dotIndex1 = index1+1;
            } else if (dotIndex1 == version1.length()) {
                val1 = 0;
            } else {
                val1 = Integer.parseInt(version1.substring(dotIndex1));
                dotIndex1 = version1.length();
            }

            int val2 = 0;
            if (index2 != -1) {
                val2 = Integer.parseInt(version2.substring(dotIndex2, index2));
                dotIndex2 = index2+1;
            } else if (dotIndex2 == version2.length()) {
                val2 = 0;
            } else {
                val2 = Integer.parseInt(version2.substring(dotIndex2));
                dotIndex2 = version2.length();
            }

            if (val1 > val2) {
                return 1;
            }

            if (val1 < val2) {
                return -1;
            }

            if (index1 == -1 && index2 == -1) {
                break;
            }
        }

        return 0;
    }
}

分断で解いた答え

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] str1 = version1.split("\\.");
        String[] str2 = version2.split("\\.");
        int max = Math.max(str1.length,str2.length);
        for(int i=0;i<max;i++){
            int num1 = i >= str1.length ? 0 : Integer.parseInt(str1[i]);
            int num2 = i >= str2.length ? 0 : Integer.parseInt(str2[i]);
            if(num1 < num2) return -1;
            if(num1 > num2) return 1;
        }

        return 0;
    }
}

Reference
https://leetcode.com/problems/compare-version-numbers/