A straight forward iterative O(n) solution


  • 3
    S
    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;
    }

Log in to reply
 

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