Understandable C++ code. 4ms AC.


  • 1
    G

    The main idea is very simple and the code consists of three phases:

    1. When version1 and version2 are not finished, compare the value of
      corresponding string before dot.
    2. If version1 is finished, check whether remaining version2 contains
      string not equal to 0
    3. If version2 is finished, check whether remaining version1 contains
      string not equal to 0

    Example1:
    version1=="11.22.33",
    version2=="11.22.22".
    11 == 11;
    22 == 22;
    33 > 22;
    return 1.

    Example2:
    version1=="11.22.33",
    version2=="11.22.33".
    11 == 11;
    22 == 22;
    33 == 33;
    return 0.

    Example3:
    version1=="11.22.33",
    version2=="11.22.33.00.00".
    11 == 11;
    22 == 22;
    33 == 33;
    remaining version2 equals to 0;
    return 0.

    Example4:
    version1=="11.22.33.00.01",
    version2=="11.22.33".
    11 == 11;
    22 == 22;
    33 == 33;
    remaining version1 contains 01;
    return 1.

    class Solution {
    public:
        int compareVersion(string version1, string version2) {
            int begin1 = 0;  //begin index for version1
            int begin2 = 0;  //begin index for version2
            
            string prefix1; //string before current dot in version1
            int prenum1;    //corresponding integer
            
            string prefix2; //string before current dot in version2
            int prenum2;    //corresponding integer
            
            
            while(begin1 < version1.size() && begin2 < version2.size())
            {
                int i = begin1;
                for(; i < version1.size(); i ++)
                {
                    if(version1[i] == '.')
                        break;
                }
                if(i < version1.size())
                    //i point to the '.' in version1
                    prefix1 = version1.substr(begin1, i-begin1);
                else
                    prefix1 = version1.substr(begin1);  //to end
                prenum1 = atoi(prefix1.c_str());
                begin1 = i+1;
                
                int j = begin2;
                for(; j < version2.size(); j ++)
                {
                    if(version2[j] == '.')
                        break;
                }
                if(j < version2.size())
                    //j point to the '.' in version2
                    prefix2 = version2.substr(begin2, j-begin2);
                else
                    prefix2 = version2.substr(begin2);
                prenum2 = atoi(prefix2.c_str());
                begin2 = j+1;
                
                if(prenum1 > prenum2)
                    return 1;
                else if(prenum1 < prenum2)
                    return -1;
            }
            //to here, version1 to end or version2 to end
            if(begin1 >= version1.size() && begin2 >= version2.size())
                return 0;
            else if(begin1 >= version1.size())
            {//version1 ended
                while(begin2 < version2.size())
                {
                    int j = begin2;
                    for(; j < version2.size(); j ++)
                    {
                        if(version2[j] == '.')
                            break;
                    }
                    if(j < version2.size())
                        //j point to the '.' in version2
                        prefix2 = version2.substr(begin2, j-begin2);
                    else
                        prefix2 = version2.substr(begin2);
                    prenum2 = atoi(prefix2.c_str());
                    if(prenum2 > 0)
                        return -1;  //version2 > version1
                    begin2 = j+1;
                }
                return 0;
            }
            else 
            {//version2 ended
                while(begin1 < version1.size())
                {
                    int i = begin1;
                    for(; i < version1.size(); i ++)
                    {
                        if(version1[i] == '.')
                            break;
                    }
                    if(i < version1.size())
                        //i point to the '.' in version1
                        prefix1 = version1.substr(begin1, i-begin1);
                    else
                        prefix1 = version1.substr(begin1);  //to end
                    prenum1 = atoi(prefix1.c_str());
                    if(prenum1 > 0)
                        return 1;   //version1 > version2
                    begin1 = i+1;
                }
                return 0;
            }
        }
    };

  • 2
    M

    Also accepted 4ms C++ solution, but code is shorter with standard lib functions.

    int compareVersion(string version1, string version2) {
            
    		version1.push_back('.');
    		version2.push_back('.');
    
    		while( !(version1.empty() && version2.empty()) )
            {
    			size_t idx1 = 0;
    			size_t idx2 = 0;
    
                int v1 = version1.empty() ? 0 : stoi(version1, &idx1);
                int v2 = version2.empty() ? 0 : stoi(version2, &idx2);
                
    			version1.erase(0, idx1+1);
    			version2.erase(0, idx2+1);
    
                if (v1 > v2)
                {
                    return 1;
                }
                else if (v1 < v2)
                {
                    return -1;
                }
            }
            
            return 0;
        }

  • 0
    G

    Thank you for sharing. SFL is so powerful!


  • 0
    W

    nice using stoi,
    but the "erase" operation seems cost O(n) for chars moving :(


Log in to reply
 

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