*Java* Recursive solution in 2ms


  • 1
    E

    There are many nice solution in iterative way, but not a recursive one, so here it is if you are interested.

    It is longer than those nice iterative solutions, but can be faster. Since those nice solutions split the two arrays, which take O(m+n) time for sure. Here, we are only looking at the leftmost part and stop whenever the comparison result is either -1 or 1.

    public class Solution {
    public int compareVersion(String version1, String version2) {
        if(version1.euqals("") && version2.equals("")) return 0; // both are "", return 0
        
        String sub1, sub2;
        int v1s, v2s;
        if(version1.equals("")) {
            v1s = 0;
            sub1 = "";
        }
        else {
            int id1 = version1.indexOf(".");
            
            if(id1==-1) {
                v1s = Integer.parseInt(version1);
                sub1 = "";
            }
            else {
                v1s = Integer.parseInt(version1.substring(0, id1));
                sub1 = version1.substring(id1+1);
            }
        }
        
        if(version2.equals("")) {
            v2s = 0;
            sub2 = "";
        }
        else {
            int id2 = version2.indexOf(".");
            if(id2==-1) {
                v2s = Integer.parseInt(version2);
                sub2 = "";
            }
            else {
                v2s = Integer.parseInt(version2.substring(0, id2));
                sub2 = version2.substring(id2+1);
            }
        }
        
        if(v1s>v2s) return 1;
        if(v1s<v2s) return -1;
        return compareVersion(sub1, sub2);
    }
    }
    

    BTW, is there any way to simplify it?


Log in to reply
 

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