LeetCode 最长公共前缀：三种解法详解

思路解析

1. 初始设置：直接用 strs[0] 做基准，因为它至少包含在结果里（如果存在）。
2. 逐个比较：遍历剩余字符串，一旦发现不匹配，立刻截断 prefix。这里有个细节，一旦 prefix 变空，后面就不用比了，直接 break 能省不少时间。
3. 返回结果：循环结束或提前退出后，返回当前的 prefix。

复杂度分析

• 时间复杂度：最坏情况下是 O(S)，其中 S 是所有字符串中字符的总和。因为每个字符最多被比较一次。
• 空间复杂度：O(1)，只用了几个变量，没有额外分配大内存。

2. 二分查找法

既然我们要找的是'最长'前缀，那前缀长度肯定在 [0, minLen] 之间。这天然适合用二分查找。我们猜测一个长度 mid，检查这个长度是否满足所有字符串都有该前缀。如果满足，说明答案可能更长；如果不满足，说明太长了，需要缩小范围。

*注意：虽然有些教程将其归类为动态规划，但核心逻辑其实是二分搜索答案，这样效率更高且更直观。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        int n = strs.size();
        int minLen = INT_MAX;
        // 先找到最短字符串的长度，作为上界
        for (const string& s : strs) {
            minLen = min(minLen, (int)s.length());
        }
        int low = 1, high = minLen;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (isCommonPrefix(strs, mid)) {
                low = mid + 1; // 尝试更长的
            } else {
                high = mid - 1; // 缩短一点
            }
        }
        return strs[0].substr(0, (low + high) / 2);
    }

private:
    bool isCommonPrefix(const vector<string>& strs, int len) {
        string prefix = strs[0].substr(0, len);
        for (int i = 1; i < strs.size(); i++) {
            // find 返回的位置如果不是 0，说明不是前缀
            if (strs[i].find(prefix) != 0) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    Solution solution;
    vector<string> strs = {"flower", "flow", "flight"};
    cout << solution.longestCommonPrefix(strs) << endl;
    return 0;
}

思路解析

1. 确定边界：先算出最短字符串长度 minLen，因为公共前缀不可能比它长。
2. 二分收缩：在 [1, minLen] 区间内二分。isCommonPrefix 负责验证当前长度是否可行。
3. 验证函数：取第一个字符串的前 len 个字符，去其他字符串里找是不是从开头就匹配。find 返回 0 表示匹配成功。
4. 结果计算：循环结束时，(low + high) / 2 即为最大合法长度。

复杂度分析

• 时间复杂度：二分查找需 O(log minLen) 次，每次验证需 O(n * minLen)。总复杂度约为 O(n * minLen * log minLen)。
• 空间复杂度：O(1)，忽略临时字符串占用的空间。

3. 纵向扫描法

这个方法更像人眼阅读。按列检查，第一列所有字符相同吗？第二列呢？遇到不同的或者某个字符串结束了，就停止。这种方法代码非常简洁，特别适合小规模数据。

代码实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

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];
    }
};

思路解析

1. 外层循环：控制列索引 i，也就是前缀的长度。
2. 内层循环：遍历所有字符串，检查第 i 列字符是否一致。
3. 终止条件：只要有一个字符串在第 i 列不匹配或长度不够，立刻返回前 i 个字符。
4. 特殊情况：如果所有列都匹配完，直接返回第一个字符串本身。

复杂度分析

• 时间复杂度：O(S)，同样需要遍历所有字符。
• 空间复杂度：O(1)。

方法对比与总结

总的来说，这三种方法各有千秋。横向扫描和纵向扫描在实际工程中都很常用，前者容易理解，后者代码量最小。二分查找则在理论性能上对长字符串有优势。实际面试或开发中，推荐优先掌握横向扫描法，它的平衡性最好。