LeetCode 最長公共前綴：垂直掃描與分治優化

問題描述

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

解法一：垂直掃描法

從第一個字符串的第一個字符開始，依次與所有其他字符串的相同位置字符比較。一旦發現不匹配或到達某字符串末尾，即返回當前公共前綴。時間複雜度 O(S)，S 為所有字符串長度之和。

解法二：水平掃描法

將第一個字符串作為初始前綴，依次與後續字符串比較縮短前綴。直觀但最壞情況下需多次遍歷。

解法三：分治法（優化）

將問題分解為左右兩半，遞歸求解各自的最長公共前綴，最後合併兩半的結果。利用「公共前綴的公共前綴」特性，減少比較次數。

解法四：二分查找法

在最短字符串長度範圍內二分查找最大公共前綴長度，每次驗證該長度前綴是否為所有字符串公共前綴。時間複雜度 O(S log m)，m 為最短字符串長度。

推薦實現：垂直掃描（C++）

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if (strs.empty()) return "";
        for (int i = 0; i < strs[0].size(); ++i) {
            char c = strs[0][i];
            for (int j = 1; j < strs.size(); ++j) {
                if (i == strs[j].size() || strs[j][i] != c)
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

關鍵點總結

• 優先處理空數組、單字符串等邊界情況
• 垂直掃描在字符差異較早時表現最佳
• 分治法適合並行化處理大規模數據
• 二分查找結合字符串切片驗證，代碼簡潔

根據數據分佈特點選擇合適算法，垂直掃描通常是工程實踐的首選。