第22章字符串中查找最长公共前缀

课程目录第22章字符串中查找最长公共前缀

第22章 · 最长公共前缀：多字符串比较

第22章 · 字符串中查找最长公共前缀：多字符串比较

最长公共前缀，说白了就是一堆字符串从第一个字符开始，最多能有多少个字符完全相同。比如 "flower"、"flow"、"flight" 的前缀是 "fl"。我当年刚入行时，总觉得这问题太简单，直接一个个比下去不就行了？后来在日志分析项目中处理上千个URL时，才发现“暴力”也有讲究，稍不留神就踩坑。

这一章，我们就从最朴素的纵向比较讲起，再聊到分治、二分等进阶思路。我会结合自己的项目经历，把那些容易翻车的地方都摊开来说。

1. 纵向扫描 —— 最直观，也最实用

思路很简单：拿第一个字符串当基准，依次比较每个位置上的字符是否和其他字符串相同。一旦发现不匹配或者某个字符串长度不够，就返回当前已经匹配的部分。

我个人习惯用这种写法，因为它够直接，而且不容易出错。来看代码：

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    // 以第一个字符串为基准
    for (int i = 0; strs[0][i] != '\0'; i++) {
        char ch = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            // 长度不够 或 字符不匹配
            if (strs[j][i] != ch || strs[j][i] == '\0') {
                strs[0][i] = '\0';  // 直接截断
                return strs[0];
            }
        }
    }
    return strs[0];
}

注意看，我直接在原字符串上截断，返回第一个字符串的起始地址。这样做的好处是省了额外空间。但有个坑：如果你后续还要用原数据，就别这么干。我在一个配置解析模块里就这么写过，结果把原始字符串改坏了，排查了半天……嗯，从那以后我习惯先复制一份，或者只返回长度。

如果字符串数量很多（比如上万条），纵向扫描的早期终止特性就特别香。平均情况下你不需要遍历所有字符，一旦发现不匹配立刻返回。

2. 分治策略 —— 把大问题切成小片

分治的思路是：把字符串数组分成两半，分别求左半边的公共前缀和右半边的公共前缀，然后再把这两个前缀合并。合并的过程其实就是再求一次两个字符串的公共前缀。

你可能会问：这比纵向扫描好在哪？其实分治在并行计算里更有优势。我在一次多核日志处理任务中用过，把字符串数组拆成多个块，每个核算一块的公共前缀，最后再合并。速度确实快了不少。

// 辅助函数：求两个字符串的公共前缀
char* commonPrefix(char* left, char* right) {
    int i = 0;
    while (left[i] && right[i] && left[i] == right[i]) {
        i++;
    }
    left[i] = '\0';
    return left;
}

char* divideAndConquer(char** strs, int l, int r) {
    if (l == r) return strs[l];
    int mid = (l + r) / 2;
    char* leftPref = divideAndConquer(strs, l, mid);
    char* rightPref = divideAndConquer(strs, mid + 1, r);
    return commonPrefix(leftPref, rightPref);
}

这里有个细节：commonPrefix 直接修改了 left 字符串。如果你不想破坏原数据，可以单独分配内存。我个人建议在算法演示中用这种就地修改的方式，但生产环境里最好用 strndup 或自己 malloc。

分治的递归深度是 logN，但每次合并都会扫描两个前缀的公共部分。总的时间复杂度依然是 O(S)，S 是所有字符串的总字符数。别被“分治”两个字迷惑，它并没有降低最坏情况下的复杂度。

3. 二分查找 —— 对最短字符串的长度下手

这个方法有点意思。先找到所有字符串中最短的那个，记长度为 minLen。然后对 minLen 进行二分：判断前 mid 个字符是不是所有字符串的公共前缀。如果是，就向右半区找；如果不是，向左半区找。

我刚开始觉得这方法有点绕，后来在面试时被问到“有没有比纵向扫描更优的解法”，我才认真琢磨了二分版本。其实它更适合那种字符串特别长、但公共前缀很短的情况。比如几百个长度为 10⁵ 的字符串，公共前缀只有几个字符，二分查找能快速缩小范围。

int isCommonPrefix(char** strs, int strsSize, int len) {
    char* prefix = strs[0];
    for (int i = 1; i < strsSize; i++) {
        for (int j = 0; j < len; j++) {
            if (prefix[j] != strs[i][j]) return 0;
        }
    }
    return 1;
}

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    int minLen = strlen(strs[0]);
    for (int i = 1; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLen) minLen = len;
    }
    int low = 0, high = minLen;
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (isCommonPrefix(strs, strsSize, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    strs[0][low] = '\0';
    return strs[0];
}

注意二分边界：我用了 (low + high + 1) / 2 取上中位数，避免死循环。这个细节我曾经在二分模板里栽过跟头，调试了半天才发现是边界没处理对。

4. 三种方法对比与选型建议

方法	时间复杂度	空间复杂度	适用场景
纵向扫描	O(S)	O(1)	通用，代码简单，字符串数量多时早停
分治	O(S)	O(logN) 递归栈	适合并行/多核处理，代码稍复杂
二分查找	O(S·log(minLen))	O(1)	字符串极长但公共前缀短，面试炫技

我个人在工程里用得最多的是纵向扫描。为什么？因为它够简单，不容易出错。而且大多数场景下字符串长度和数量都适中，纵向扫描的提前退出机制非常高效。分治我只有在需要利用多核时才用。二分查找嘛……说实话，我更多是在面试时写，或者用来处理那种超长DNA序列片段。

        记住一个原则：不要为了优化而优化。先写出正确的纵向扫描，如果性能瓶颈真的出现在这里，再考虑分治或二分。我见过太多人一上来就搞分治，结果递归爆栈或者合并逻辑写错。
    

5. 避坑指南 & 个人经验

空数组与空字符串：如果 strsSize 为 0，直接返回空字符串。如果某个字符串是空串，公共前缀必然是空串。我习惯在函数开头就处理这些边界。
不要越界访问：纵向扫描时，一定要先检查当前列是否超出了某个字符串的长度。我曾经在循环里忘了判断 strs[j][i] == '\0'，结果读到了脏数据，返回了错误的前缀。
修改原字符串的风险：就像前面说的，如果你在函数里直接截断 strs[0]，调用方可能会遭殃。我在一个配置加载模块里就这么干过，导致后续解析全乱套。建议要么返回新分配的内存，要么只返回长度。
字符编码问题：如果是 UTF-8 等多字节编码，按字节比较可能会出错。不过大部分面试题和内部工具都是纯 ASCII，这点暂时不用太担心。

我记得有一次在分析服务器日志时，需要从几千条 URL 中提取公共路径前缀。一开始我用纵向扫描，跑得飞快。后来数据量涨到几十万条，我换成了分治+多线程，速度提升了将近 3 倍。但说实话，如果单线程的话，分治并没有比纵向扫描快多少。所以选型一定要结合你的实际运行环境。

6. 小结

最长公共前缀这个问题，看似简单，但里面藏着不少细节。纵向扫描是基石，分治让你看到分而治之的魅力，二分查找则展示了如何利用有序性来优化。我个人建议你把三种方法都手写一遍，体会它们在不同数据下的表现。

最后送你一句话：写算法题时，多想一步边界；写工程代码时，多想一步维护。这样你写的代码才能既快又稳。

📚 课程目录