C++ 0ms iterative and recursive simple solutions


  • 0
    Z
    class Solution {
    public:
    int compareVersion(string version1, string version2) {
        //return solution1(version1, version2);       //iterative
        return solution2(version1, -1, version1.length(), version2, -1, version2.length());       //recursive
    }
    private:
    int solution1(string v1, string v2) {
        int sz1 = v1.length(), sz2 = v2.length(), num1(0), num2(0), i1(-1), i2(-1);
        while(i1 < sz1 && i2 < sz2){            //compare numbers when both not reach end of string
            num1 = getNum(v1, ++i1, sz1);
            num2 = getNum(v2, ++i2, sz2);
            if(num1 != num2) return num1 > num2 ? 1 : -1;
        }
        if(num1 != num2) return num1 > num2 ? 1 : -1;   //compare last numbers before loop breaks
        while(i1 < sz1)         //check remaining numbers for version 1 if has
            if(getNum(v1, ++i1, sz1) != 0) return 1;
        while(i2 < sz2)         //check remaining numbers for version 2 if has
            if(getNum(v2, ++i2, sz2) != 0) return -1;
        return 0;               //equai if all remaining numbers are 0s or no remaining numbers
    }
    int getNum(string v, int &pos, int sz){     //get number based on '.' and lengh of string
        int num(0);
        while(pos < sz){
            if(v[pos] == '.') break;
            num = 10 * num + (v[pos++] - '0');
        }
        return num;
    }
    int solution2(string v1, int i1, int len1, string v2, int i2, int len2){
        if(i1 == len1 && i2 == len2) return 0;
        if(i1 == len1) while(getNum(v2, ++i2, len2) != 0) return -1;
        else if(i2 == len2) while(getNum(v1, ++i1, len1) != 0) return 1;
        else{
            int num1 = getNum(v1, ++i1, len1), num2 = getNum(v2, ++i2, len2);
            if(num1 != num2) return num1 > num2 ? 1 : -1;
        }
        return solution2(v1, i1, len1, v2, i2, len2);
    }
    };

  • 0
    M

    I found something wrong when casing:

    "2147483646.0"
    "2147483648.0"

    Your answer:1 Expected answer:-1

    But the OJ doesn't test this case.


  • 0
    Z

    thanks a lot!!!
    I think the solution will be using substring for each number instead of int or long (in case your version number is even larger) to compare, but comparing strings will cause more time. Hope this will help.


Log in to reply
 

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