LeetCode 14. 最长公共前缀

◎

本节目标

逐列同步检查多个字符串，在首次不一致处返回公共前缀。

这道题对应字符串基础解题框架的多串同步扫描。公共前缀由每一列是否在所有字符串中相同决定，第一次不一致的位置就是答案边界。

查看原题

朴素思路及瓶颈

对每个字符串两两求公共前缀也能得到答案，但会反复切片和比较。排序后只比较字典序首尾两串是另一种方法，却改变了输入并增加排序成本。逐列检查不排序输入，正好与问题的结构一致。

同步扫描不变量

设第一串当前列的字符为基准。已经通过的所有列都在每个字符串中存在且相同；一旦某个字符串已经结束，或同列字符不同，当前列不能属于公共前缀，应返回此前的部分。单个空串的答案是空串，空字符串列表也可直接返回空串。

代码实现

两份实现均以第一串为列基准，内层遍历所有字符串，首次不一致立即返回；没有排序或修改输入。

C++

C++17

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

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) {
            return "";
        }

        for (size_t column = 0; column < strs[0].size(); column++) {
            char expected = strs[0][column];
            for (const string& word : strs) {
                if (column == word.size() || word[column] != expected) {
                    return strs[0].substr(0, column);
                }
            }
        }
        return strs[0];
    }
};

Python

Python 3

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        if not strs:
            return ""

        for column, expected in enumerate(strs[0]):
            for word in strs:
                if column == len(word) or word[column] != expected:
                    return strs[0][:column]
        return strs[0]

复杂度分析

• 时间复杂度：O(S)，其中 S 是被检查的总字符数；最坏为所有字符串总长度。
• 空间复杂度：O(1)，不计返回字符串。

易错点

• 某个字符串比当前列短时仍访问该下标。
• 把“最长公共前缀”误做成任意位置的最长公共子串。
• 为方便比较而排序输入，违背了不需要改变输入的约束。

模式迁移

多串同步扫描可以迁移到共同目录、共同编码头或字典批量前缀查询。若字符串集合需要频繁动态查询，则应考虑 Trie，让共享前缀由路径结构保存。