C语言实现最长公共前缀

以下是C语言实现查找字符串数组最长公共前缀的代码：

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

char* longestCommonPrefix(char** strs, int strsSize) {
    // 处理空数组情况
    if (strsSize == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }

    // 获取第一个字符串作为基准
    char* first = strs[0];
    size_t len = strlen(first);

    // 为结果分配内存（长度不超过基准字符串）
    char* result = malloc(len + 1);
    int i;

    // 纵向扫描所有字符串
    for (i = 0; i < len; i++) {
        char current = first[i];
        
        // 检查后续字符串的对应位置
        for (int j = 1; j < strsSize; j++) {
            /* 关键判断：当出现以下情况时停止扫描
               1. 当前字符串长度不足
               2. 字符不匹配 */
            if (strs[j][i] != current) {
                goto end;  // 跳出所有循环
            }
        }
        result[i] = current;  // 记录当前匹配的字符
    }

end:
    result[i] = '\0';  // 添加字符串终止符
    return result;
}

/* 测试代码 */
int main() {
    char* test1[] = {"flower", "flow", "flight"};
    char* test2[] = {"dog", "racecar", "car"};
    char* test3[] = {"", "abc"};
    char* test4[] = {"abc"};
    
    printf("测试1: %s\n", longestCommonPrefix(test1, 3));  // 输出"fl"
    printf("测试2: %s\n", longestCommonPrefix(test2, 3));  // 输出""
    printf("测试3: %s\n", longestCommonPrefix(test3, 2));  // 输出""
    printf("测试4: %s\n", longestCommonPrefix(test4, 1));  // 输出"abc"

    // 记得释放内存（演示时省略）
    return 0;
}

逐行解析：

1. 函数入口处理：

if (strsSize == 0) {
    char* result = malloc(1);
    result[0] = '\0';
    return result;
}

• 处理空数组的特殊情况
• 分配1字节内存存放空字符串

2. 基准字符串获取：

char* first = strs[0];
size_t len = strlen(first);

• 以第一个字符串为比较基准
• 获取基准字符串长度用于循环控制

3. 内存分配：

char* result = malloc(len + 1);

• 分配足够存储最长可能前缀的内存（基准字符串长度+1）
• +1用于存放字符串终止符'\0'

4. 纵向扫描循环：

for (i = 0; i < len; i++) {
    char current = first[i];

• 逐个字符检查基准字符串的每个位置
• current存储当前需要匹配的字符

5. 内层校验循环：

for (int j = 1; j < strsSize; j++) {
    if (strs[j][i] != current) {
        goto end;
    }
}

• 关键逻辑：检查所有其他字符串的当前位置
• j从1开始跳过基准字符串
• 任一字符串出现长度不足或字符不匹配立即终止

6. 字符记录与终止：

result[i] = current;  // 记录匹配字符

• 所有字符串当前位置匹配时记录该字符

end:
result[i] = '\0';

• 统一处理字符串终止符
• 自动处理全匹配、提前终止、空字符串等情况

算法特点：

• 时间复杂度：O(S)，S为所有字符串字符总数
• 空间复杂度：O(1)（不考虑返回字符串占用的空间）
• 提前终止机制：发现不匹配立即停止扫描
• 内存安全：始终保证返回字符串正确终止

执行结果：

测试1: fl
测试2: 
测试3: 
测试4: abc

常见问题处理：

1. 空数组：直接返回空字符串
2. 单元素数组：返回该字符串副本
3. 基准字符串为空：立即返回空字符串
4. 中间字符串较短：自动终止扫描
5. 完全匹配：返回整个基准字符串

注意：调用者需负责释放返回字符串的内存，实际使用时应添加内存释放代码。