怎么查找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 是字符總數。

總結

選擇合適的方法取決于具體場景和字符串特征。對于小規模數據，簡單直觀的水平/垂直掃描即可；大規模數據可考慮分治或二分查找優化。 “`