Search code examples
cfunctioncharc-stringslongest-substring

Why does this code work as expected if I use Visual C(Visual Sudio 2022) but doesn't if I use gcc 8.2?


I am new to C and still learning(currently doing some "LeetCode" challenges). I wrote a function that should return the longest common prefix in an array of strings. I tested with a couple different values and all works fine. But a string array {"aaa", "aa", "aaa"} will result in "aa" (Correct) in Visual Studio but "aaa" in the gcc version and I do not understand why.

LeetCode Output(uses gcc 8.2 with gcc11 standard) My Visual Studio 2022 Output using

Here is my code:

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

char* longestCommonPrefix(char** strs, int strsSize) {

    char* result = calloc(200, sizeof(char));
    if (result == NULL) return NULL;
    size_t result_length = strlen(strs[0]);
    memcpy(result, strs[0], result_length);
    char* result_end = result + result_length + 1;


    for (size_t i = 1; i < strsSize; ++i) {
        char* ptr_res = result;
        char* ptr_cur = strs[i];

        while (*ptr_res == *ptr_cur && *ptr_res > '\0' && *ptr_cur > '\0') {
            ++ptr_res;
            ++ptr_cur;
        }

        result_end = ptr_res;
    }
    *result_end = '\0';
    return result;
}


int main(int argc, char* argv[]) {
    char* a[3];
    a[0] = "aaa";
    a[1] = "aa";
    a[2] = "aaa";

    char* b = longestCommonPrefix(a, 2);
    printf(b);
    free(b);
}

@Chris; @EricPostpischil; @VladFromMoscow;

Thank you for pointing out my flaws. I learned a lot form you all. I marked the answer from @EricPostpischil as the solution cause I tested it and it worked for this challenge. The answer of @VladFromMoscow is great and it seems a lot better for code I would actually deploy so I will definetly take notes.

For reference here is the working code I submitted to LeetCode and it worked well:

char* longestCommonPrefix(char** strs, int strsSize) {

    char* result = calloc(200, sizeof(char));
    if (result == NULL) return NULL;
    size_t result_length = strlen(strs[0]);
    memcpy(result, strs[0], result_length);
    char* result_end = result + result_length;


    for (size_t i = 1; i < strsSize; ++i) {
        char* ptr_res = result;
        char* ptr_cur = strs[i];

        while (*ptr_res == *ptr_cur && ptr_res < result_end) {
            ++ptr_res;
            ++ptr_cur;
        }

        result_end = ptr_res;
    }
    *result_end = '\0';
    return result;
}

Solution

  • This is wrong:

    char* result_end = result + result_length + 1;
    

    result_length contains the number of characters in strs[0] before the null character, and result_end is used to set the null character later, so it should point to where the null character will go:

    char* result_end = result + result_length;
    

    Then this code:

    while (*ptr_res == *ptr_cur && *ptr_res > '\0' && *ptr_cur > '\0') {
    

    allows the loop to progress until the end of the string currently in the result buffer or the current string it is being compared to. That can be further than the longest common prefix established so far. The loop should be limited to the length of the longest common prefix:

    while (*ptr_res == *ptr_cur && ptr_res < result_end) {
    

    Observe that testing for null/non-null characters is not needed. If a null character is encountered in ptr_cur, then either *ptr_cur differs from *ptr_res or we have reached the end of the string in result, which result_end already points to (initially) or before (if it was updated from a prior comparison).

    Also *ptr_res > '\0' is an incorrect way to test for a non-null character, as character values can be negative. *ptr_res != '\0' is a proper test.

    printf(b); is hazardous, as it is prone to misbehavior if b is mishandled. Also, it is generally preferable to terminate program output with a new-line character. Use puts(b) or printf("%s\n", b);.