[LeetCode 165] Compare Version Number

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

Difficulty: easy Analysis: This question is to test the skills of string to int and int to string convention. In C++, parsing string (e.g., parse string according to ' , ') as well as int to string operation can be done using the stringstream.
In python, it is much easier since we have int() and str() methods to do so.

The idea of this problem could be considered to compare two list of numbers that are separated by '.' Note that when comparing list with different length, if they are the same for the 1st part, if the longer list have all 0s in its tail, then those two lists are the same. E.g., 1.0.000.0 and 1, two lists generated are [1,0,0,0], and [1]. And it is necessary to check "all" digits instead of checking only the "next" digits because if there exists one digit that is not 0, the two numbers are not equal.

// 封装一个split函数去取'.'分开的每个字段 vector &split(const string &s, char delim) { vector elems; stringstream ss(s); string token; while(getline(ss, token, delim)) { elems.push_back(atoi(item.c_str())); } return elems; }

// Time: O(n) // Space: O(n) class Solution { public: int compareVersion(string version1, string version2) { istringstream st1(version1); istringstream st2(version2); string token; vector d1; vector d2; while (getline(st1,token,'.')){ stringstream os1; os1.str(token); int tmp; os1 >> tmp; d1.push_back(tmp); } while (getline(st2,token,'.')){ stringstream os2; os2 << token; int tmp; os2 >> tmp; d2.push_back(tmp); }

    int n1 = d1.size(), n2 = d2.size();

    for (int i = 0;i < min(n1, n2); i++){
        if (d1[i] > d2[i]) return 1;
        if (d1[i] < d2[i]) return -1;
    }

    if (n1 < n2){
        for (int i = n1; i < n2; i++){
            if (d2[i] != 0) return -1;
        }
        return 0;
    }
    if (n1 > n2){
        for (int i = n2; i < n1; i++){
            if (d1[i] != 0) return 1;
        }
        return 0;
    }
    if (n1 == n2){return 0;}
}

};

// Time: O(n) // Space: O(1) class Solution { public: int compareVersion(string version1, string version2) { int n1 = version1.size(), n2 = version2.size(); for (int i = 0, j = 0; i < n1 || j < n2; ++i, ++j){

        int num1 = 0, num2 = 0;
        while (version1[i] != '.' && i < n1)
            num1 = num1 * 10 + (version1[i++] - '0');

        while (version2[j] != '.' && j < n2)
            num2 = num2 * 10 + (version2[j++] - '0');

        if (num1 > num2)
            return 1;

        if (num1 < num2)
            return -1;
      }

    return 0;
}

};

// Compare two strings directly when they are with the same length! // string a="123", b="012"; // bool c = a > b; // we get true // if they are not with the same length, insert '0' on the left side to // make them have the same length and them compare directly.

class Solution { public: int compareVersion(string version1, string version2) { int n1 = version1.size(), n2 = version2.size(); int i = 0, j = 0; while(i < n1 || j < n2){ string t1 = { "0" }, t2 = { "0" };

        while(i < n1 && version1[i] != '.') t1.push_back(version1[i++]);
        i++;

        while(j < n2 && version2[j] != '.') t2.push_back(version2[j++]);
        j++;

        // make two strings with equal length
        if (t1.size() > t2.size()) t2.insert(t2.begin(), t1.size() - t2.size(), '0');
        else if (t1.size() < t2.size()) t1.insert(t1.begin(), t2.size() - t1.size(), '0');
        else{};

        //compare two substring
        if (t1 > t2) return 1;
        else if (t1 < t2) return -1;
        else continue;
    }// end of while()
    return 0;
}

};