LeetCode 最長公共前綴：橫向掃描與縱向比較的優雅實現

問題描述

給定一個字符串數組，找出所有字符串共有的最長前綴。若不存在公共前綴，返回空字符串。

核心觀察

最長公共前綴的長度不可能超過數組中最短字符串的長度。因此，我們可以先找出最短長度 minLen，然後只需檢查前 minLen 個字符。

算法流程

1. 處理邊界情況：空數組直接返回空串。
2. 遍歷數組求得 minLen。
3. 雙重循環驗證：外層遍歷字符位置 j (0 到 minLen-1)，內層遍歷所有字符串，比較第 j 個字符是否與第一個字符串相同。
4. 若發現不匹配，立即結束並返回已構建的前綴。
5. 若所有位置均匹配，返回完整前綴。

代碼實現 (Java)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        int minLen = strs[0].length();
        for (String s : strs) {
            minLen = Math.min(minLen, s.length());
        }
        StringBuilder res = new StringBuilder();
        for (int j = 0; j < minLen; j++) {
            char c = strs[0].charAt(j);
            for (int k = 1; k < strs.length; k++) {
                if (strs[k].charAt(j) != c) {
                    return res.toString();
                }
            }
            res.append(c);
        }
        return res.toString();
    }
}

複雜度分析

• 時間複雜度：O(S)，其中 S 為所有字符串長度之和。最壞情況下需比較所有字符。
• 空間複雜度：O(1)，僅使用常數額外空間（不計輸出）。

優化方向

可採用分治法、二分查找長度或 Trie 樹優化，但對於大多數場景，縱向掃描已足夠高效且代碼簡潔。