C++ solution without integer number conversions


  • 0
    C

    I'm afraid that the atoi solutions are not reliable enough because the version string may be extremely long and overflow the integer value. Thus I try to use only pointers but the complexity becomes 2n and takes 2 ms.

    int compareVersion(std::string version1, std::string version2) {
        const char *head1 = version1.c_str(), *head2 = version2.c_str();
        const char *tail1 = head1, *tail2 = head2;
        for (;;) {
            // ignore leading zeros
            while (*head1 == '0') {
                ++head1;
            }
            while (*head2 == '0') {
                ++head2;
            }
    
            // tokenize
            tail1 = head1;
            while ((*tail1 != '.') && (*tail1 != '\0')) {
                ++tail1;
            }
            tail2 = head2;
            while ((*tail2 != '.') && (*tail2 != '\0')) {
                ++tail2;
            }
    
            // compare lengths
            if ((tail1 - head1) > (tail2 - head2)) {
                return 1;
            } else if ((tail1 - head1) < (tail2 - head2)) {
                return -1;
            }
    
            // compare digits
            while (head1 < tail1) {
                if (*head1 > *head2) {
                    return 1;
                } else if (*head1 < *head2) {
                    return -1;
                }
                ++head1;
                ++head2;
            }
    
            if ((*head1 == '\0') && (*head2 == '\0')) {
                break;
            }
            if (*head1 != '\0') {
                ++head1;
            }
            if (*head2 != '\0') {
                ++head2;
            }
        }
        return 0;
    }

Log in to reply
 

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