0ms C++ solution with detailed explanation


  • 0
    I

    My solution is a little bit complicated because I don't use something like 'atoi' which will make the problem much more easier. If we use atoi there would be a limit: the number between two '.' has at most 32 bits, though it works in all test cases in this problem.
    Here is my solution

    void cut_tail(string &version) {
        int end_pos = version.size() - 1;
        while (version.rfind(".", end_pos) != string::npos) {
    	    int i = end_pos;
    	    while (version[i] == '0') i--;
    	    if (version[i] == '.') end_pos = i - 1;
    	    else break;
        }
        version = version.substr(0, end_pos + 1);
    }
    
    int compareVersion(string version1, string version2) {
        int last_pos1 = 0, last_pos2 = 0, pos1 = 0, pos2 = 0;
        cut_tail(version1);    // (1)
        cut_tail(version2);
        while (true) {
    	    pos1 = version1.find(".", last_pos1);
    	    pos2 = version2.find(".", last_pos2);
    	    pos1 = pos1 == string::npos ? version1.size() : pos1;    // (2)
    	    pos2 = pos2 == string::npos ? version2.size() : pos2;
    	    while (last_pos1 < pos1 - 1 && version1[last_pos1] == '0') last_pos1++;    // (3)
    	    while (last_pos2 < pos2 - 1 && version2[last_pos2] == '0') last_pos2++;
    	    if (pos1 - last_pos1 > pos2 - last_pos2) return 1;    // (4)
    	    else if (pos1 - last_pos1 < pos2 - last_pos2) return -1;
    	    for (int i = 0; i < pos1 - last_pos1; i++) {    // (5)
    		    if (version1[last_pos1 + i] > version2[last_pos2 + i]) return 1;
    		    else if (version1[last_pos1 + i] < version2[last_pos2 + i]) return -1;
    	    }
    	    if (pos1 == version1.size() && pos2 == version2.size()) break;    // (6)
    	    last_pos1 = pos1 + 1;
    	    last_pos2 = pos2 + 1;
        }
        return 0;
    }
    

    (1) First, we preprocess version1 and version2, cut meaningless suffix. For example, "1.0.0.3.0.0.0" should be cut into "1.0.0.3".

    (2) If we cannot find "." any more, we set pos to the length of the version.

    (3) We skip prefix 0s in a segment. For example, we may have "0000123". The prefix 0s should be taken away.

    (4) After we take away prefix zeroes, we ought to have two segments with same length if they are equal. If they don't have the same length, the longer one must be larger.

    (5) Then we check every bit of two segments.

    (6) Both two versions come to end, they are equal.


Log in to reply
 

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