Wednesday, August 26, 2015

Leetcode: Compare Version Numbers

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

Understand the problem:
The tricky part of the problem is to understand that 1.0 and 1 are the same version. 

Code (Java):
public class Solution {
    public int compareVersion(String version1, String version2) {
        if ((version1 == null || version1.length() == 0) && 
            (version2 == null || version2.length() == 0)) {
            return 0;
        }
        
        if (version1 == null || version1.length() == 0) {
            return -1;
        }
        
        if (version2 == null || version2.length() == 0) {
            return 1;
        }
        
        String delim = "[.]";
        String[] v1 = version1.split(delim);
        String[] v2 = version2.split(delim);
        
        int i;
        int j;
        for (i = 0, j = 0; i < v1.length || j < v2.length; i++, j++) {
            String s1 = "";
            String s2 = "";
            if (i < v1.length) {
                s1 = v1[i];
            }
            
            if (j < v2.length) {
                s2 = v2[j];
            }
            
            s1 = removeLeadingZeros(s1);
            s2 = removeLeadingZeros(s2);
            
            if (s1.isEmpty() && s2.isEmpty()) {
                continue;
            }
            
            if (s2 == null || s2.length() == 0) {
                return 1;
            }
            
            if (s1 == null || s1.length() == 0) {
                return -1;
            }
            
            if (s1.length() > s2.length()) {
                return 1;
            } else if (s1.length() < s2.length()) {
                return -1;
            } else {
                for (int k = 0; k < s1.length(); k++) {
                    if (Character.getNumericValue(s1.charAt(k)) > 
                        Character.getNumericValue(s2.charAt(k))) {
                        return 1;
                    } else if (Character.getNumericValue(s1.charAt(k)) < 
                        Character.getNumericValue(s2.charAt(k))) {
                        return -1;
                    }
                }
            }
        }
        
        return 0;
    }
    
    private String removeLeadingZeros(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                break;
            } else {
                start++;
            }
        }
        
        return s.substring(start);
    }
}

A neater code:
If in each sub-version, we assume that the length is not greater than the upper bound of an integer number, we don't need to parse it character-by-character. 

Code (Java):
public int compareVersion(String version1, String version2) {
    String[] arr1 = version1.split("\\.");
    String[] arr2 = version2.split("\\.");
 
    int i=0;
    while(i<arr1.length || i<arr2.length){
        if(i<arr1.length && i<arr2.length){
            if(Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])){
                return -1;
            }else if(Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])){
                return 1;
            }
        } else if(i<arr1.length){
            if(Integer.parseInt(arr1[i]) != 0){
                return 1;
            }
        } else if(i<arr2.length){
           if(Integer.parseInt(arr2[i]) != 0){
                return -1;
            }
        }
 
        i++;
    }
 
    return 0;
}

Update on 10/14/15:
The very tricky part is the corner cases need to consider:
1. v1 = 1.0.0, v2 = 1, => so they should be the same version

Therefore, when we went through one of the arrays, we need to also iterate the rest of the array until it's to the end. 

Code (Java):
public class Solution {
    public int compareVersion(String version1, String version2) {
        String delim = "[.]";
        String[] v1 = version1.split(delim);
        String[] v2 = version2.split(delim);
        
        int i = 0; 
        int j = 0;
        
        while (i < v1.length && j < v2.length) {
            int seg1 = Integer.parseInt(v1[i]);
            int seg2 = Integer.parseInt(v2[j]);
            
            if (seg1 > seg2) {
                return 1;
            } else if (seg1 < seg2) {
                return -1;
            } else {
                i++;
                j++;
            }
        }
        
        while (i < v1.length) {
            int seg1 = Integer.parseInt(v1[i]);
            if (seg1 != 0) {
                return 1;
            } else {
                i++;
            }
        }
        
        while (j < v2.length) {
            int seg2 = Integer.parseInt(v2[j]);
            if (seg2 != 0) {
                return -1;
            } else {
                j++;
            }
        }
        
        return 0;
    }
}

Update on 11/20/18:
class Solution {
    public int compareVersion(String version1, String version2) {
        String delim = "[.]";
        String[] s1 = version1.split(delim);
        String[] s2 = version2.split(delim);
        
        int i = 0;
        int j = 0;
        
        while (i < s1.length || j < s2.length) {
            int i1 = 0;
            int i2 = 0;
            if (i < s1.length) {
                i1 = Integer.parseInt(s1[i]);
            }
            
            if (j < s2.length) {
                i2 = Integer.parseInt(s2[j]);
            }
            
            if (i1 == i2) {
                i++;
                j++;
            } else {
                return i1 - i2 < 0 ? -1 : 1;
            }
        }
        
        return 0;
    }
}

No comments:

Post a Comment