求字符数组内最长公共前缀

以下是一个示例实现：

public static String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) {
                return "";
            }
        }
    }
    return prefix;
}

算法思路：

我们将第一个字符串作为前缀，然后逐个比较后面的字符串是否有相同的前缀，如果没有，则将前缀缩短，直到找到公共前缀或者前缀为空。时间复杂度为 $O(nk)$，其中 $n$ 是字符串数组的长度，$k$ 是字符串中最长的字符数。

相关问题

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

可以用二分查找来求解字符串数组中的最长公共前缀。具体思路如下：

1. 先找到字符串数组中长度最短的字符串，这个字符串的长度就是最长公共前缀的上限。

2. 用二分查找的方式，不断缩小最长公共前缀的上限，直到找到最长公共前缀为止。

具体实现可以参考以下代码：

def longestCommonPrefix(strs):
    if not strs:
        return ""
    min_len = min(map(len, strs))
    left, right = 0, min_len
    while left < right:
        mid = (left + right + 1) // 2
        prefix = strs[0][:mid]
        if all(s.startswith(prefix) for s in strs):
            left = mid
        else:
            right = mid - 1
    return strs[0][:left]

其中，`left` 和 `right` 分别表示最长公共前缀的下限和上限，初始化为 0 和最短字符串的长度。在二分查找的过程中，取中间位置 `mid`，并判断字符串数组中是否所有字符串都以长度为 `mid` 的前缀开头。如果是，说明最长公共前缀的长度可以增加，将 `left` 更新为 `mid`；否则，最长公共前缀的长度需要缩小，将 `right` 更新为 `mid - 1`。最后返回第一个字符串的前 `left` 个字符即可。

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