LeetCode 最长公共前缀解题思路与代码实现

代码解析

1. 初始设置：将 strs[0] 作为初始公共前缀 prefix。
2. 逐个比较：遍历剩余的字符串，每次更新 prefix 为其与当前字符串的公共前缀。
3. 返回结果：当 prefix 缩减为 0 时，立即返回空字符串；否则返回最终公共前缀。

时间复杂度计算

• 最坏情况：所有字符串长度相等且无公共前缀时，时间复杂度为 O(S)，其中 S 是数组中所有字符的总和。
• 平均情况：由于每次比较时前缀逐渐缩短，通常能达到 O(minLen * n) 的效率，minLen 为字符串中最小长度，n 为字符串个数。

空间复杂度

仅使用常数额外空间，空间复杂度为 O(1)。

方法 2：二分查找法

此问题可转化为二分查找问题，在可能的公共前缀长度范围内进行搜索。

1. 确定范围：找到最短字符串的长度，设为 minLen，搜索范围为 [1, minLen]。
2. 状态转移：如果长度为 mid 的前缀是所有字符串的公共前缀，则尝试更长的长度；否则尝试更短的长度。
3. 初始条件：第一个字符串为基准，依次向后验证。

代码实现

#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++) {
            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. 二分搜索：通过二分法逐步缩小范围，判断当前长度是否是公共前缀。
3. 判断公共前缀：利用 isCommonPrefix 函数检查当前长度 len 是否为公共前缀。
4. 返回结果：最终获得的 (low + high) / 2 即最长公共前缀长度。

时间复杂度分析

• 二分查找的复杂度为 O(log minLen)，每次查找调用 isCommonPrefix 的时间复杂度为 O(n * minLen)。因此总复杂度为 O(n * minLen * log minLen)。
• 空间复杂度为 O(1)。

方法 3：纵向扫描法

逐列检查每个字符是否相同，遇到不同则停止。这种方法直观易懂，适用于小规模字符串数组。

代码实现

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

方法对比与总结

• 横向扫描法和纵向扫描法都适合中小规模数据，横向法代码更简洁。
• 二分查找法提升了效率，适用于需要更高效率的情况。