4 ms runtime C++ easy to understand solution with algorithm description


  • 8
    S

    Here's the algorithm:
    Assumption is that the strings are properly formatted so no checking.
    Valid strings are 123, 01, 123.01.5.16
    I extracted the string into a C style char array for speed.
    Scan both the strings one sub-version at a time in a loop if result is still 0 and one (or both) of the strings still have characters left to parse. So basically, once the result is 1 or -1 we don't need further parsing. I'm using strtol so that we can pick each sub-version number and move the scan pointer to the "." preceding next sub-version number. If one of the strings is done before the other (example: 1.0 and 1) then make sure to the sub-version of finished string to 0.

    int compareVersion(string version1, string version2) {
    	int result = 0;
    	char *vStr1 = (char*) version1.c_str();
    	char *vStr2 = (char*) version2.c_str();
    
    	while (result == 0 && (*vStr1 != '\0' || *vStr2 != '\0')) {
    		long v1 = *vStr1 == '\0' ? 0 : strtol(vStr1, &vStr1, 10);
    		long v2 = *vStr2 == '\0' ? 0 : strtol(vStr2, &vStr2, 10);
    		if (v1 > v2) result = 1;
    		else if (v2 > v1) result = -1;
    		else {
    			if (*vStr1 != '\0') vStr1++;
    			if (*vStr2 != '\0') vStr2++;
    		}
    	}        
    
        return result;
    }

  • 4
    C

    Some useful introduction for strtol

    strtol c++ reference

    <cstdlib>

    long int strtol (const char* str, char** endptr, int base);

    Convert string to long integer

    Parses the C-string str interpreting its content as an integral number of the specified base, which is returned as a long int value. If endptr is not a null pointer, the function also sets the value of endptr to point to the first character after the number.

    The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes as many characters as possible that are valid following a syntax that depends on the base parameter, and interprets them as a numerical value. Finally, a pointer to the first character following the integer representation in str is stored in the object pointed by endptr.

    If the value of base is zero, the syntax expected is similar to that of integer constants, which is formed by a succession of:

    • An optional sign character (+ or -)
    • An optional prefix indicating
      octal or hexadecimal base ("0" or "0x"/"0X" respectively)
    • A sequence
      of decimal digits (if no base prefix was specified) or either octal
      or hexadecimal digits if a specific prefix is present

    If the base value is between 2 and 36, the format expected for the integral number is a succession of any of the valid digits and/or letters needed to represent integers of the specified radix (starting from '0' and up to 'z'/'Z' for radix 36). The sequence may optionally be preceded by a sign (either + or -) and, if base is 16, an optional "0x" or "0X" prefix.

    If the first sequence of non-whitespace characters in str is not a valid integral number as defined above, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

    For locales other than the "C" locale, additional subject sequence forms may be accepted


Log in to reply
 

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