Compare Version Numbers.java

M
1521777505
tags: String

给两串version number,  由数字和'.' 组成. 比较先后顺序. 

If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

#### divide and conquer 
- 用 str.split("\\.") 分割string
- Convert成integer, 逐个击破

#### 注意
- '1.0' 和 '0' 是相等的
- 如果可以假设version integer都是valid, 直接Integer.parseInt()就可以了
- 不然的话, 可以compare string

```
/*
Compare two version numbers version1 and version2.
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
*/

/*
Thoughts:
- divide and conqure: divide by '.'
- during the same cun, the one with no sub-division, it's the leading version
- use Integer.parseInt() with assumption that the numbers are valid integer.
*/
class Solution {
    public int compareVersion(String version1, String version2) {
        if (version1.equals(version2)) {
            return 0;
        }
        String[] subVersion1 = version1.split("\\.");
        String[] subVersion2 = version2.split("\\.");
        int size = Math.max(subVersion1.length, subVersion2.length);
        int rst = 0;
        for (int i = 0; i < size; i++) {
            if (i >= subVersion1.length) {
                rst = Integer.parseInt(subVersion2[i]) == 0 ? 0 : -1; // assume the missing subVersion1 = 0
            } else if (i >= subVersion2.length) {
                rst = Integer.parseInt(subVersion1[i]) == 0 ? 0 : 1; // assume the missing subVersion2 = 0
            } else { // both exist
                if (Integer.parseInt(subVersion1[i]) != Integer.parseInt(subVersion2[i])) {
                    rst = Integer.parseInt(subVersion1[i]) < Integer.parseInt(subVersion2[i]) ? -1 : 1;    
                }
            }
            if (rst != 0) {
                return rst;
            }
        }
        return rst;
    }
}


/*
Thoughts:
- divide and conqure: divide by '.'
- during the same cun, the one with no sub-division, it's the leading version
- compare string
*/
class Solution {
    public int compareVersion(String version1, String version2) {
        if (version1.equals(version2)) {
            return 0;
        }
        if (!version1.contains(".") && !version2.contains(".")) {
            return compareString(version1, version2);
        }
        String[] subVersion1 = version1.split("\\.");
        String[] subVersion2 = version2.split("\\.");
        int size = Math.max(subVersion1.length, subVersion2.length);
        int rst = 0;
        for (int i = 0; i < size; i++) {
            if (i >= subVersion1.length) {
                rst = compareString("0", subVersion2[i]);    
            } else if (i >= subVersion2.length) {
                rst = compareString(subVersion1[i], "0");
            } else {
                rst = compareString(subVersion1[i], subVersion2[i]);    
            }
            if (rst != 0) {
                return rst;
            }
        }
        return rst;
    }
    
    /*
        Assume the number can be super large, and can't be saved in Integer, or Long.
        Compare number by each digit
    */
    private int compareString(String str1, String str2) {
        if (str1.equals(str2)) {
            return 0;
        }
        while (str1 != null && str1.length() > 1 && str1.charAt(0) == '0') {
            str1 = str1.substring(1);
        }
        
        while (str2 != null && str2.length() > 1 && str2.charAt(0) == '0') {
            str2 = str2.substring(1);
        }
        
        if (str1.length() != str2.length()) {
            return str1.length() < str2.length() ? -1 : 1;
        }
        for (int i = 0; i < str1.length(); i++) {
            int digit1 = str1.charAt(i) - '0';
            int digit2 = str2.charAt(i) - '0';
            if (digit1 < digit2) {
                return -1;
            } else if (digit1 > digit2) {
                return 1;
            }
        }
        return 0;
    }
}
```