LeetCode 14：最長公共前綴 —— 多種解法對比與優化

題目

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

核心思路對比

推薦實現：縱向掃描（最優常數）

class Solution {
public:
    string longestCommonPrefix(vector<string>& 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];
    }
};

排序法（代碼最短）

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(strs.begin(), strs.end());
        string &first = strs.front(), &last = strs.back();
        int i = 0;
        while (i < first.size() && i < last.size() && first[i] == last[i]) ++i;
        return first.substr(0, i);
    }
};

Python 精簡版

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs: return ""
        for i, chars in enumerate(zip(*strs)):
            if len(set(chars)) > 1:
                return strs[0][:i]
        return min(strs)  # 全匹配時返回最短串

# 分治法 44ms
    def longestCommonPrefix(self, strs):
        if not strs: return ""
        def lcp(l, r):
            if l == r: return strs[l]
            mid = (l + r) // 2
            left, right = lcp(l, mid), lcp(mid+1, r)
            i = 0
            while i < len(left) and i < len(right) and left[i] == right[i]: i += 1
            return left[:i]
        return lcp(0, len(strs)-1)

關鍵優化點

1. 早退：發現不匹配立即返回，避免多餘比較。
2. 基準選擇：用最短串作基準可減少循環次數。
3. 避免 substr 複製：C++ 中用 string_view (C++17) 或索引範圍延遲構造結果。

複雜度總結

• 時間：O(S)，S 為所有字符總數。
• 空間：O(1)（不計輸出），排序法 O(log N) 棧空間。