Online judge pass -- java version


  • 0
    R

    key edge cases:

    1. multiple "."
    2. do not use numbers to avoid overflow
    3. remove beginning zeros
    public class Solution {
        public int compareVersion(String version1, String version2) {
            
            int v1Start = 0;
            int v1End = 0;
            
            int v2Start = 0;
            int v2End = 0;
            
            // loop per sequence split by "."
            while (!(v1Start > version1.length() && v2Start > version2.length())) {
                String v1Unit = null;
                String v2Unit = null;
                v1End = version1.indexOf(".", v1Start);
                if (v1End == -1) {
                    v1End = version1.length();
                }
                
                v2End = version2.indexOf(".", v2Start);
                if (v2End == -1) {
                    v2End = version2.length();
                }
                
                if (v1Start < v1End) {
                    v1Unit = version1.substring(v1Start, v1End);
                }
                
                if (v2Start < v2End) {
                    v2Unit = version2.substring(v2Start, v2End);
                }
                
                int compareResult =  compare(v1Unit, v2Unit);
                if (compareResult > 0) {
                    return 1;
                } else if (compareResult < 0) {
                    return -1;
                }
                v1Start = v1End+1;
                v2Start = v2End+1;
            }
            return 0;
        }
        
        
        // compare string instead of covertting it to numbers, which can overflow
        private int compare(String v1, String v2) {
            v1 = normalize(v1);
            v2 = normalize(v2);
            if (v1.length() > v2.length()) {
                return 1;
            } else if (v1.length() < v2.length()) {
                return -1;
            }
            for (int i=0; i<v1.length(); i++) {
                if (v1.charAt(i) > v2.charAt(i)) {
                    return 1;
                } else if (v1.charAt(i) < v2.charAt(i)) {
                    return -1;
                }
            }
            return 0;
        }
        
        // remove beginning 0 
        private String normalize(String s) {
            if (s == null) {
                return "0";
            }
            s = s.trim();
            int start = 0;
            while (start < s.length()-1 && s.charAt(start) == '0'){
                start++;
            }
            return s.substring(start, s.length());
        }
    }

Log in to reply
 

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