Longest Common Prefix - C Solution

1. Introduction

This post explores a common string manipulation problem in C programming - finding the longest common prefix (LCP) among an array of strings. This problem is a classic example of array and string processing and is particularly useful in applications like auto-completion and text analysis.

Problem

Given an array of strings strs, the task is to find the longest common prefix string amongst these strings. If there is no common prefix, the function should return an empty string "".

2. Solution Steps

1. Handle the edge case where the array is empty.

2. Initialize the prefix as the first string in the array.

3. Iterate over the array and update the prefix.

4. For each string, compare it with the current prefix and update the prefix to the common part.

5. Return the prefix after processing all strings.

3. Code Program

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

// Function to find the longest common prefix
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";

    char* prefix = strs[0];
    for (int i = 1; i < strsSize; i++) {
        int j = 0;
        while (strs[i][j] && prefix[j] && strs[i][j] == prefix[j]) {
            j++;
        }
        prefix[j] = '\0'; // Update the prefix up to the common part
    }
    return prefix;
}

// Main function to test the longestCommonPrefix function
int main() {
    char* strs1[] = {"flower", "flow", "flight"};
    printf("Longest Common Prefix (Example 1): %s\n", longestCommonPrefix(strs1, 3));

    char* strs2[] = {"dog", "racecar", "car"};
    printf("Longest Common Prefix (Example 2): %s\n", longestCommonPrefix(strs2, 3));

    return 0;
}

Output:

Longest Common Prefix (Example 1): fl
Longest Common Prefix (Example 2):

Explanation:

1. if (strsSize == 0) return ""; - Check if the array is empty.

2. char* prefix = strs[0]; - Initialize the prefix as the first string.

3. for (int i = 1; i < strsSize; i++) - Iterate through the array of strings.

4. while (strs[i][j] && prefix[j] && strs[i][j] == prefix[j]) - Compare the string with the current prefix.

5. prefix[j] = '\0'; - Update the prefix to the common part found.

6. return prefix; - Return the longest common prefix.

7. The main function tests the longestCommonPrefix function with two examples and prints the results.