LeetCode 14 Longest Common Prefix：最長公共前綴

題目翻譯

編寫函數找出字串陣列中的最長公共前綴。

解題思路

1. 先找出最短字串長度 minSize 及其索引 minIndex。
2. 從 minSize 遞減至 0，取最短字串前 i 字符作為候選 result。
3. 遍歷所有字串比較前 i 字符，若全部相等則返回 result。

C# 實現

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        int len = strs.Length;
        if (len == 0) return "";
        if (len == 1) return strs[0];
        int minSize = int.MaxValue, minIndex = 0;
        for (int i = 0; i < len; ++i)
            if (strs[i].Length < minSize) { minSize = strs[i].Length; minIndex = i; }
        for (int i = minSize; i >= 0; --i) {
            string result = strs[minIndex].Substring(0, i);
            int j = 0;
            for (; j < len; ++j) {
                if (j == minIndex) continue;
                if (strs[j].Substring(0, i) != result) break;
            }
            if (j == len) return result;
        }
        return "";
    }
}

優化方向

• 縱向掃描：逐字符比較所有字串同位置字符，遇不等立即返回，平均更快。
• 分治法：左右遞歸求 LCP，再合併。
• 二分查找長度 + 判斷是否為公共前綴。