1

So I am completly new to the C language. I come from a Visual Basic and C# background, languages where I usually don't need to care about low-level stuff. Recently started to learn about pointers and I am doing some of the leetcode challenges to get some practice.

**Here is the challenge text: ** Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Here is my attempt:

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

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 1) return strs[0];

    if (strs[0] == "") return "";

    char* result = strs[0];
    size_t result_length = strlen(result) - 1;
    char* result_end = strs[0] + result_length;

    for (size_t i = 1; i < strsSize; ++i) {
        
        size_t length = strlen(strs[i]) - 1;
        
        if (length < 1) return "";
        
        if (length < result_length) {
            result_end = strs[0] + length;
            result_length = length;
        }

        char* temp1 = result;
        char* temp2 = strs[i];

        while (*temp1 == *temp2 && temp1 < result_end) {
            ++temp1;
            ++temp2;
        }

        if (temp1 < result_end) {
            result_end = temp1 - 1;
            result_length -= strlen(result_end) - 1;
        }
    }

    *(result_end + 1) = '\0';
    
    return result;
}


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

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

Why do I get a write access violation error on the line *(result_end + 1) = '\0'; ? Googling this I found articles saying c strings are readonly, why tho and what would be a work around? Also any general C tips or links to such things are appreciated, thank you.

EDIT: Thanks @Chris for the solution. Here is my new code which works just fine. Also thanks at @@WeatherVane for a general C tip, I also included his knowledge into my new code.

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

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 1) return strs[0];

    if (strs[0][0] == 0) return "";

    char* result = _strdup(strs[0]);
    size_t result_length = strlen(result) - 1;
    char* result_end = strs[0] + result_length;

    for (size_t i = 1; i < strsSize; ++i) {

        char* str = _strdup(strs[i]);
        
        size_t length = strlen(str) - 1;
        
        if (length < 1) return "";
        
        if (length < result_length) {
            result_end = str + length;
            result_length = length;
        }

        char* temp = result;

        while (*temp == *str && temp < result_end) {
            ++temp;
            ++str;
        }

        if (temp < result_end) {
            result_end = temp - 1;
            result_length -= strlen(result_end) - 1;
        }
    }

    *(result_end + 1) = '\0';
    
    return result;
}


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

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


OldCrow
  • 37
  • 6
  • 1
    I get no compiler warnings and the program prints `fl`. But this `if (strs[0] == "")` is not the way to compare strings in C. You must use `strcmp()` or in this case, check `if (strs[0][0] == 0)` – Weather Vane Jun 30 '23 at 21:51
  • @WeatherVane Maybe you have a different compiler, I use Visual C(Visual Studio). And thanks for the tip with the string comparison. – OldCrow Jul 01 '23 at 07:03
  • Using MS Visual C 64-bit 2022 (without IDE). – Weather Vane Jul 01 '23 at 10:51

1 Answers1

0

It means you've written to some memory you shouldn't.

In main you have an array of char pointers. But each points to a string literal which is const char *.

In longestCommonPrefix you then attempt to modify these string literals, which invokes undefined behavior.

If you wish to modify these values in your longestCommonPrefix function, you should copy these string literals into allocated memory. The strdup is a very straightforward way to do this, as long as you ensure you free the dynamically allocated memory afterwards.

char *a[3];
a[0] = strdup("flower");
a[1] = strdup("flight");
a[2] = strdup("flow");

If you're tools don't allow use of this function, you can either declare a to hold 3 fixed length strings, or manually handle the dynamic memory allocation and copying.

Chris
  • 26,361
  • 5
  • 21
  • 42
  • 1
    For legacy reasons, the type of a string literal in C is an array of `char`, not `const char`, and it is automatically converted, where appropriate, to `char *`, not `const char *`. Students should not be taught to expect `const char *` because they cannot rely on the compiler catching mistakes through the type qualifiers. The C standard does not define the behavior if a program attempts to modify a string literal. That means it is avoided in portable code, but it also means a C implementation can support modifying a string literal if its implementors desire. – Eric Postpischil Jun 30 '23 at 21:59
  • 1
    Possibly the most dangerous thing code with UB can do: work as expected. – Chris Jun 30 '23 at 22:12
  • 1
    Note that `strdup()` becomes a part of Standard C in C23 (as does `strndup()`). – Jonathan Leffler Jul 01 '23 at 00:44
  • Thanks all for the information. @Chris your solution works just fine but for the leetcode challenge I do not have access to the main so I just added that to the function. Also I got a warning strdup is deprecated and I should rather use _strdup cause it is ISO standard. Anyway thank you very much. I will add my new code to the question for clarity. – OldCrow Jul 01 '23 at 07:16