C语言算法-最长公共前缀_c语言最长公共前缀

1 题目

2 函数实现

char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空，则返回空字符串
    if (strsSize == 0) {
        char* result = (char*)malloc(1);
        result[0] = '\0';
        return result;
    }

    // 遍历第一个字符串的每个字符
    for (int i = 0; i < strlen(strs[0]); i++) {
        char currentChar = strs[0][i];

        // 检查其他字符串在当前位置是否与第一个字符串匹配
        for (int j = 1; j < strsSize; j++) {
            if (i >= strlen(strs[j]) || strs[j][i] != currentChar) {
                // 如果不匹配，返回当前找到的公共前缀
                char* result = (char*)malloc(i + 1);
                strncpy(result, strs[0], i);
                result[i] = '\0';
                return result;
            }
        }
    }

    // 如果遍历完第一个字符串，返回第一个字符串作为最长公共前缀
    return _strdup(strs[0]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3 完整测试代码

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

// 查找字符串数组中的最长公共前缀
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串数组为空，则返回空字符串
    if (strsSize == 0) {
        char* result = (char*)malloc(1);
        result[0] = '\0';
        return result;
    }

    // 遍历第一个字符串的每个字符
    for (int i = 0; i < strlen(strs[0]); i++) {
        char currentChar = strs[0][i];

        // 检查其他字符串在当前位置是否与第一个字符串匹配
        for (int j = 1; j < strsSize; j++) {
            if (i >= strlen(strs[j]) || strs[j][i] != currentChar) {
                // 如果不匹配，返回当前找到的公共前缀
                char* result = (char*)malloc(i + 1);
                strncpy(result, strs[0], i);
                result[i] = '\0';
                return result;
            }
        }
    }

    // 如果遍历完第一个字符串，返回第一个字符串作为最长公共前缀
    return _strdup(strs[0]);
}

int main() {
    // 示例用法
    char* strings[] = { "flower", "flow", "flight" };
    int size = sizeof(strings) / sizeof(strings[0]);

    char* result = longestCommonPrefix(strings, size);

    // 打印结果
    printf("最长公共前缀是：%s\n", result);

    // 释放动态分配的内存
    free(result);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50