Monday, January 26, 2015

Compare Version Numbers

Compare Version Numbers
Compare two version numbers version1 and version1.
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
------------------------------------- think --------------------------------------------
About string to int, always remember that string can be "01" which will equal to 1 !!! Natural number doesn't allow the first bit to be 0, but string can.
------------------------------------------------------codes ------------------------------------------------------

class Solution {
public:
    int compareVersion(string version1, string version2) {
        string delimiter = ".";
        size_t pos1;
        size_t pos2;
        while ((pos1 = version1.find(delimiter)) != string::npos) {
            string v1 = version1.substr(0, pos1);
            pos2 = version2.find(delimiter);
            if (pos2 != string::npos) {
                string v2 = version2.substr(0, pos2);
                int num1 = stoi(v1);
                int num2 = stoi(v2);
                if (num1 > num2) {
                    return 1;
                } else if (num1 < num2) {
                    return -1;
                } else {
                    version1.erase(0, pos1 + delimiter.length());
                    version2.erase(0, pos2 + delimiter.length());
                }
            } else {
                if (stoi(v1) < stoi(version2)) {
                    return -1;
                } else if (stoi(v1) > stoi(version2)) {
                    return 1;
                } else {
                    version1.erase(0, pos1 + delimiter.length());
                    pos1 = version1.find(delimiter);
                    if (pos1 != string::npos) {
                        v1 = version1.substr(0, pos1);
                    } else {
                        v1 = version1;
                    }
                    if (stoi(v1) == 0) {
                        return 0;
                    } else {
                        return 1;
                    }
                }
            }
        }
     
        pos2 = version2.find(delimiter);
        if (pos2 != string::npos) {
            string v2 = version2.substr(0, pos2);
            if (stoi(version1) > stoi(v2)) {
                return 1;
            } else if (stoi(version1) < stoi(v2)) {
                return -1;
            } else {
                version2.erase(0, pos2+delimiter.length());
                pos2 = version2.find(delimiter);
                string v2;
                if (pos2 != string::npos) {
                    v2 = version2.substr(0, pos2);
                } else {
                    v2 = version2;
                }
                if (stoi(v2) == 0) {
                    return 0;
                } else {
                    return -1;
                }
            }
        } else {
            if (stoi(version1) < stoi(version2)) {
                return -1;
            } else if (stoi(version1) > stoi(version2)) {
                return 1;
            } else {
                return 0;
            }
        }
     
    }
};

----------------------------------------------------- good codes -----------------------------------------------
int compareVersion(string version1, string version2) { int m = version1.size(), n = version2.size(); int i = 0, j = 0; while (i < m && j < n) { int s1 = i; while(i < m && version1[i] != '.') ++i; string str1 = version1.substr(s1, i - s1); ++i; int s2 = j; while(j < n && version2[j] != '.') ++j; string str2 = version2.substr(s2, j - s2); ++j; int val1 = atoi(str1.c_str()); int val2 = atoi(str2.c_str()); if (val1 > val2) return 1; else if (val1 < val2) return -1; } while(i < m) { if (version1[i] != '.' && version1[i] != '0') return 1; ++i; } while(j < n) { if (version2[j] != '.' && version2[j] != '0') return -1; ++j; } return 0; }

--------------------------------------- good codes --------------------------------------------
My idea is to truncate the string by . mark, and compare the integer between every two .s. By adding some extra manipulation about string::npos, it's a valid and clean solution.
int compareVersion(string version1, string version2) {

    while (!version1.empty() || !version2.empty()) {

        string::size_type pos1 = version1.find('.');
        string::size_type pos2 = version2.find('.');

        string int1_str = version1.substr(0, pos1);
        string int2_str = version2.substr(0, pos2);

        int int1 = (int1_str.empty()) ? 0 : std::stoi(int1_str);
        int int2 = (int2_str.empty()) ? 0 : std::stoi(int2_str);

        if (int1 > int2) return 1;

        else if (int1 < int2) return -1;

        else {

            version1 = (pos1 == string::npos) ? "" : version1.substr(pos1 + 1);
            version2 = (pos2 == string::npos) ? "" : version2.substr(pos2 + 1);

        }

    }

    return 0;
}

No comments:

Post a Comment