最长公共前缀 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1

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

输出："fl"

示例 2

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

输出：""

输入不存在公共前缀。

💭 模拟答题者思考

1. 暴力：枚举所有可能的前缀长度，对每个长度检查是否每个字符串都以该前缀开头——能过，但重复比较很多。

2. 找重复：公共前缀就是「所有串开头相同的最长一段」，每多一个串，只需看当前候选前缀还能不能匹配。

3. 横向扫描：用 strs[0] 当初始 prefix，依次与后面每个串比对；不匹配就不断砍掉 prefix 最后一位，直到匹配或变空。

4. 另一种等价思路是纵向扫描：固定列下标 i，看所有串第 i 个字符是否都与 strs[0][i] 相同，一旦某串更短或字符不同就停。

5. 还可排序后只比首尾串，或建字典树；本题数据规模下横向/纵向扫描 O(S)（S 为所有字符总数）最直观。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`prefix`	str	定义：当前已确认、所有已处理字符串共同拥有的前缀维护：初始为 `strs[0]`，每引入一个新串就按需缩短更新：若 `s` 不以 `prefix` 开头，则 `prefix = prefix[:-1]` 直到匹配或为空
`s`	str	定义：当前正在与 `prefix` 比对的字符串维护：按顺序遍历 `strs[1:]` 更新：每轮取下一个字符串；若 `prefix` 已空可提前结束
`i`	int	定义（纵向扫描写法）：当前比对的字符列下标维护：从 0 开始，以 `strs[0][i]` 为基准字符更新：所有串在位置 `i` 字符一致则 `i++`，否则停止；答案为 `strs[0][:i]`

⌨️ 落码步骤

1. 特判空数组；令 prefix = strs[0]

2. 遍历 strs[1:] 中每个字符串 s

3. 当 prefix 非空且 s 不以 prefix 开头时，prefix = prefix[:-1]

4. 若 prefix 已空，提前返回 ""

5. 全部比对完毕，返回 prefix

💻 代码实现

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        prefix = strs[0]          # 当前公共前缀候选
        for s in strs[1:]:
            # 不匹配就缩短前缀，直到 s 以 prefix 开头或 prefix 为空
            while prefix and not s.startswith(prefix):
                prefix = prefix[:-1]
            if not prefix:
                return ""
        return prefix

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string prefix = strs[0];
        for (int k = 1; k < (int)strs.size(); ++k) {
            const string& s = strs[k];
            while (!prefix.empty() && s.compare(0, prefix.size(), prefix) != 0) {
                prefix.pop_back();
            }
            if (prefix.empty()) return "";
        }
        return prefix;
    }
};
// 时间 O(S)，空间 O(1)（不计输入）

📈 复杂度分析

时间复杂度 O(S)

空间复杂度 O(1)

⚠️ 常见坑

❗ 不能用 min(len(strs)) 直接当答案长度——还要保证每个位置字符都相同，不能只比长度。

❗ 纵向扫描时注意某串长度不足时 i 会越界，应先判断 i < len(s)。

❗ 空数组要返回 ""；单元素数组应返回该元素本身（即整个字符串）。

🔍 必测边界 Case

Case 1：有公共前缀

["flower","flow","flight"] → "fl"

Case 2：无公共前缀

["dog","racecar","car"] → ""

Case 3：单元素 / 空前缀

["a"] → "a"；["ab","a"] → "a"（较短串决定上限）