1

So I am solving the "Longest Common Prefix" problem on Leetcode in C and have almost got it working. My Code:

    char * longestCommonPrefix(char ** strs, int strsSize){
    int minlen = strlen(strs[0]);
    for(int i=0; i<strsSize; i++){
        int len = strlen(strs[i]);
        if(len<minlen){
            minlen=len;
        }
    }

    int len=0;
    for(int i=0; i<minlen; i++){
        int match=1;
        char check = strs[0][i];
        for(int j=0; j<strsSize; j++){
            if(strs[j][i]!=check){
                match=0;
                break;
            }
        }
        if(match==0){
            break;
        }
        else{
            len++;
        }
    }

    if(len==0){
        return "";
    }
    
    char ret[len];
    for(int i=0; i<len; i++){
        ret[i] = strs[0][i];
    }
    for(int i=0; i<len; i++){
        printf("%c",ret[i]);
    }
    return ret;
}

Printing out the array ret is working out and is giving expected output. But when I am returning the char array ret, it is returning (null). So the array is storing the value correctly, but there is some issue with returning it. Can someone please help with this?

Improve this question
5
  • 7
    ret goes out of scope when longestCommonPrefix() returns. It effectively doesn’t exist anymore. Either pass a pointer to the buffer in to populate it or dynamically allocate it. Commented Mar 24, 2024 at 12:19
  • 2
    Also, regardless of scope ret is not NUL terminated. Commented Mar 24, 2024 at 12:28
  • Thank you for helping, the issue was a mix of two things you pointed out. I had already tried dynamically allocating ret with malloc before but it was running into an error when doing so. The issue as you also pointed out was ret not being Null terminated. When doing both together it did submit successfully. Commented Mar 24, 2024 at 12:50
  • @PaulLynch: Objects do not have scope. And an object may exist and be accessible in code in which its identifier is not in scope. Commented Mar 24, 2024 at 13:01
  • @Confused Coder Just a note, it’s bad practice to return(“”); in one case and a pointer to a dynamically allocated buffer in another. The calling function should free memory if allocated by longestCommonPrefix() but it doesn’t know if the pointer returned points to allocated memory or a string literal (unless it “knows” a zero-length string is a literal). Best not to mix and match; Vlad’s answer avoids the problem. Commented Mar 24, 2024 at 14:10

1 Answer 1

Reset to default
0

If the function returns only a pointer

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

then it should return a pointer to a string. The local variable length array ret declared like

char ret[len];

is not built to store a string.

Moreover it will not be alive after exiting the function because it has automatic storage duration. As a result the returned pointer will be invalid and dereferencing it will invoke undefined behavior.

On the other hand, in this return statement

if(len==0){
    return "";
}

you are returning a string (string literal) that has static storage duration.

You need to allocate memory dynamically for the resulted string in the both cases.

Also this code snippet

int minlen = strlen(strs[0]);
for(int i=0; i<strsSize; i++){
    int len = strlen(strs[i]);
    if(len<minlen){
        minlen=len;
    }
}

is just redundant. Pay attention to that you should use the unsigned integer type size_t instead of the signed type int for string lengths.

And to copy one character array in another character array it is better to use standard C string function memcpy instead of using a manually written loop.

The function can look for example the following way

char * longestCommonPrefix( char **s, size_t n )
{
    char *result = NULL;

    if (n != 0)
    {
        size_t len = 0;

        if (n == 1)
        {
            len = strlen( s[0] );
        }
        else
        {
            for (int equal = 1; equal && s[0][len] != '\0'; len += equal)
            {
                size_t i = 1;

                while (i < n && s[i][len] == s[0][len]) ++i;

                equal = i == n;
            }
        }

        result = malloc( len + 1 );

        if (result != NULL)
        {
            memcpy( result, s[0], len );
            result[len] = '\0';
        }
    }

    return result;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

The idiomatic solution is to pass in pointer to a buffer to receive a result. Hiding a memory allocation on a function requires the caller to know it was allocated and makes it responsible for cleaning up. It is screaming "memory leak".
@Clifford What will be the size of the buffer you are going to pass? There are two approaches: either the function itself allocates memory as strdup does or you youself provide a buffer. It is similarly to standard C++ algorithms where can be two variants: one is named without suffix _copy and other with the suffix _copy. The both are idiomatic.
@Clifford It would be better if the function returned the length of the common prefix. However the function is initially declared as declared.:)
All true, but C++ has features that allow that to be done more safely, such as destructors and smart-pointers. Here the caller is made responsible for any clean-up, and perhaps that should be made clear. All that said, it is a Leetcode problem, not a real world problem, so I am not sure I should care. My opinion of Leetcode "success" as a measure of code quality or coder ability is pretty low.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.