C语言实现最长公共前缀

大家好，欢迎来到IT知识分享网。

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

#include 
  
    #include 
   
     #include 
    
      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. 完全匹配：返回整个基准字符串

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