LeetCode Longest Common Prefix 最長公共前綴 (縱向掃描)

問題

給定字符串數組，求最長公共前綴。若無公共前綴返回空串。數組長度 0~n。

算法

縱向掃描：取第一個字符串作為基準，逐字符檢查所有其他字符串在該位置是否相同。遇到不匹配或越界即停止。也可橫向掃描：LCP(s1..sn) = LCP(LCP(s1,s2), s3)...

代碼 (C++)

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

複雜度

O(S) 時間，S 為所有字符串長度之和。O(1) 額外空間 (不計輸出)。

邊界處理

• 空數組 → ""
• 單字符串 → 該字符串
• 包含空串 → ""