怎么查找Java字符串最长的公共前缀

# 怎么查找Java字符串最长的公共前缀

在编程中，查找一组字符串的最长公共前缀（Longest Common Prefix, LCP）是一个常见问题。本文将介绍几种在Java中实现这一功能的方法，并分析它们的优缺点。

## 问题描述

给定一个字符串数组，找出所有字符串共有的最长前缀。例如：

- 输入：`["flower","flow","flight"]`
- 输出：`"fl"`

如果不存在公共前缀，则返回空字符串 `""`。

## 方法一：水平扫描法

### 实现步骤
1. 以第一个字符串作为初始公共前缀 `prefix`。
2. 遍历剩余字符串，逐个与 `prefix` 比较，更新 `prefix` 为两者的公共前缀。
3. 如果 `prefix` 为空，提前终止循环。

### 代码示例
```java
public 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(S)，其中 S 是所有字符串字符总数。

方法二：垂直扫描法

实现步骤

1. 逐个字符比较所有字符串的同一位置。
2. 当字符不匹配或某个字符串到达末尾时停止。

代码示例

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];
}

时间复杂度

• 最优情况：O(n*minLen)，其中 minLen 是最短字符串长度。

方法三：分治法

实现步骤

1. 将字符串数组分成左右两部分。
2. 分别递归求解左右两部分的公共前缀。
3. 合并左右结果得到最终公共前缀。

代码示例

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    return divideAndConquer(strs, 0, strs.length - 1);
}

private String divideAndConquer(String[] strs, int left, int right) {
    if (left == right) return strs[left];
    int mid = (left + right) / 2;
    String lcpLeft = divideAndConquer(strs, left, mid);
    String lcpRight = divideAndConquer(strs, mid + 1, right);
    return commonPrefix(lcpLeft, lcpRight);
}

private String commonPrefix(String a, String b) {
    int minLen = Math.min(a.length(), b.length());
    for (int i = 0; i < minLen; i++) {
        if (a.charAt(i) != b.charAt(i)) {
            return a.substring(0, i);
        }
    }
    return a.substring(0, minLen);
}

时间复杂度

• 与水平扫描法相同，但更适合并行处理。

方法四：二分查找法

实现步骤

1. 找到最短字符串长度 minLen。
2. 在 [0, minLen] 范围内进行二分查找。
3. 检查中间值是否为所有字符串的公共前缀。

代码示例

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs) {
        minLen = Math.min(minLen, str.length());
    }
    int low = 1, high = minLen;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (isCommonPrefix(strs, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len) {
    String prefix = strs[0].substring(0, len);
    for (int i = 1; i < strs.length; i++) {
        if (!strs[i].startsWith(prefix)) {
            return false;
        }
    }
    return true;
}

时间复杂度

• O(S*log n)，其中 S 是字符总数。

总结

选择合适的方法取决于具体场景和字符串特征。对于小规模数据，简单直观的水平/垂直扫描即可；大规模数据可考虑分治或二分查找优化。 “`