LeetCode 14 最長公共前綴：橫向掃描法詳解與 Java 實現

題目描述

編寫一個函數，查找字符串數組中的最長公共前綴。若不存在公共前綴，返回空字符串 ""。

核心思路：橫向掃描

將數組第一個字符串作為初始公共前綴 prefix，依次與後續字符串比較，取兩者的公共部分更新 prefix。若某次比較後 prefix 為空，直接返回。

算法步驟

1. 邊界檢查：數組為空或長度為 0，返回 ""。
2. 令 prefix = strs[0]。
3. 遍歷 i = 1 ~ n-1：
   用雙指針 j 同時遍歷 strs[i] 與 prefix，統計相同字符長度。
   若 j == 0 則無公共前綴，返回 ""。
   截取 prefix = prefix.substring(0, j)。
4. 遍歷結束返回 prefix。

Java 參考實現

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            while (j < strs[i].length() 
                   && j < prefix.length() 
                   && strs[i].charAt(j) == prefix.charAt(j)) {
                j++;
            }
            if (j == 0) {
                return "";
            }
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
}

複雜度分析

• 時間復雜度：O(S)，S 為所有字符串長度之和。最壞情況需比較所有字符。
• 空間復雜度：O(1)，僅使用常數額外空間。

延伸思考

此外還有縱向掃描、分治法、二分查找法、字典樹等多種解法，各有優劣。橫向掃描代碼簡潔，工程實踐中常用。