C语言实现查找字符串数组中的最长公共前缀

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

int main()
{
    char strs[100][100] = {"flower", "flow", "flight"};
    int n = 3, i, j;
    char prefix[100] = "";
    
    for (i = 0; strs[0][i] != '\0'; i++) {
        for (j = 1; j < n; j++) {
            if (strs[j][i] != strs[0][i]) {
                prefix[i] = '\0'; // 不匹配，清空前缀
                break;
            }
        }
        if (j == n) {
            prefix[i] = strs[0][i];
        } else {
            break;
        }
    }
    
    printf("The longest common prefix is: %s\n", prefix);
    
    return 0;
}

相关问题

c语言用二分查找求字符串数组最长公共前缀

二分查找求字符串数组的最长公共前缀可以用以下思路：

首先，我们需要找到字符串数组中长度最短的字符串，因为最长公共前缀不会超过这个字符串的长度。

然后，我们使用二分查找算法，从字符串数组中找到一个长度为 mid 的前缀字符串，判断这个前缀字符串是否是所有字符串的公共前缀。如果是公共前缀，那么我们将左端点 left 更新为 mid+1；否则，我们将右端点 right 更新为 mid-1。

最终，当 left > right 时，我们就找到了最长的公共前缀。

以下是使用 C 语言实现的代码：

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

// 求字符串数组中最长的公共前缀
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";

    // 找到字符串数组中长度最短的字符串
    int minLen = strlen(strs[0]);
    for (int i = 1; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLen) minLen = len;
    }

    // 二分查找
    int left = 0, right = minLen;
    while (left <= right) {
        int mid = (left + right) / 2;

        // 判断长度为 mid 的前缀字符串是否是所有字符串的公共前缀
        int i;
        for (i = 1; i < strsSize; i++) {
            if (strncmp(strs[i], strs[0], mid) != 0) {
                break;
            }
        }

        if (i == strsSize) {
            left = mid + 1;  // 是公共前缀，将左端点更新为 mid+1
        } else {
            right = mid - 1;  // 不是公共前缀，将右端点更新为 mid-1
        }
    }

    // 返回最长的公共前缀
    char* result = (char*)malloc((right + 1) * sizeof(char));
    strncpy(result, strs[0], right);
    result[right] = '\0';
    return result;
}

int main() {
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;
    char* result = longestCommonPrefix(strs, strsSize);
    printf("Longest Common Prefix: %s\n", result);
    free(result);
    return 0;
}

输出结果：

Longest Common Prefix: fl

编写一个函数来查找字符串数组中的最长公共前缀c语言

char* longestCommonPrefix(char** strs, int strsSize) {
if (strsSize == 0) { // 如果字符串数组为空，则返回空字符串
return "";
}
int len = strlen(strs[0]); // 获取第一个字符串的长度
for (int i = 0; i < len; i++) {
char ch = strs[0][i]; // 获取第一个字符串的第i个字符
for (int j = 1; j < strsSize; j++) { // 遍历其它字符串
if (i >= strlen(strs[j]) || strs[j][i] != ch) { // 如果其它字符串长度小于i或者第i个字符不同
strs[0][i] = '\0'; // 则将第一个字符串的第i个字符置为'\0'
return strs[0]; // 返回当前前缀
}
}
}
return strs[0]; // 返回第一个字符串，即为最长公共前缀
}