力扣-14. 最长公共前缀（Longest Common Prefix）

最后编辑于2025-06-19

14. 最长公共前缀（Longest Common Prefix）

Easy

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，则返回空字符串 ""。

示例 1：

输入： strs = ["flower","flow","flight"]
输出： "fl"

示例 2：

输入： strs = ["dog","racecar","car"]
输出： ""

约束：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 由小写英文字母组成

思路与常见解法

此题没有复杂的数据结构，常见解法包括：

  • 纵向扫描（逐列比较）：以第一个字符串为基准，逐列比较其它字符串对应位置的字符，遇到不匹配或某个字符串到达末尾即停止，时间复杂度 O(S)（S 为所有字符总数）。

  • 横向扫描（逐个字符串缩减前缀）：将当前公共前缀与下一个字符串比较并逐步缩减，直到与所有字符串匹配。

  • 排序法：对字符串数组按字典序排序，最长公共前缀必出现在排序后首尾两个字符串之间，比较首尾的公共前缀即可，时间复杂度 O(n log n + L)（L 为比较长度）。

  • 分治法：将数组分成两半，分别求各自最长公共前缀，再合并，类似归并思想，复杂度 O(S)。

下面给出几种实现。

方法一：纵向扫描（逐列比较）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string res = "";
        for (int j = 0; j < strs[0].size(); ++j) {
            char c = strs[0][j];
            for (int i = 1; i < strs.size(); ++i) {
                if (j >= strs[i].size() || strs[i][j] != c) {
                    return res;
                }
            }
            res.push_back(c);
        }
        return res;
    }
};
  • 时间复杂度： O(S)
  • 空间复杂度： O(1)

方法二：简洁的纵向扫描（遇到不匹配直接返回 substr）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int j = 0; j < strs[0].size(); ++j) {
            for (int i = 0; i < strs.size(); ++i) {
                if (j >= strs[i].size() || strs[i][j] != strs[0][j]) {
                    return strs[0].substr(0, j);
                }
            }
        }
        return strs[0];
    }
};

方法三：排序法（比较首尾字符串）

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(strs.begin(), strs.end());
        int i = 0, len = min(strs[0].size(), strs.back().size());
        while (i < len && strs[0][i] == strs.back()[i]) ++i;
        return strs[0].substr(0, i);
    }
};
  • 说明： 排序法巧妙地把问题简化为比较两端字符串，适合于需要处理大量相似字符串的场景。

作者想说的话：
最长公共前缀问题通常用纵向扫描或排序法即可解决：纵向扫描直观且高效（按需停止），排序法在某些场景代码更简洁。