Description

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 "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

Answer & Explaining

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

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

    // Start with the first string as the prefix
    char* prefix = strs[0]; //初始化前綴
    int prefixLength = strlen(prefix); //前綴長度

    // Iterate over the rest of the strings
    //從1到strsSize,i=1是因為strs[0]是前綴初始化
    for (int i = 1; i < strsSize; i++) { 
        int j = 0;
        // Compare the current string with the prefix
        //j不超過前綴長度且當前字串與prefix[j]相等
        while (j < prefixLength && strs[i][j] == prefix[j]) {
            j++;//新增j
        }
        // Update the prefix length to the matched length
        prefixLength = j; //長度更新

        // If there is no common prefix, return an empty string
        if (prefixLength == 0) {
            return ""; //前綴皆不同則回傳空字串
        }
    }

    // Allocate memory for the result and copy the prefix
    //malloc動態分配記憶體位置給result
    char* result = (char*)malloc((prefixLength + 1) * sizeof(char)); 
    //將prefix陣列的前prefixlength字元複製到result
    strncpy(result, prefix, prefixLength);
    result[prefixLength] = '\0';//最後一位為\0

    return result;//回傳最長前綴
}

Testing

int main() {
    char* strs1[] = {"flower", "flow", "flight"};
    int strsSize1 = 3;
    char* result1 = longestCommonPrefix(strs1, strsSize1);
    printf("Longest common prefix: %s\n", result1);
    free(result1);  // Free the allocated memory

    char* strs2[] = {"dog", "racecar", "car"};
    int strsSize2 = 3;
    char* result2 = longestCommonPrefix(strs2, strsSize2);
    printf("Longest common prefix: %s\n", result2);
    free(result2);  // Free the allocated memory

    return 0;
}