最长公共字符串后缀这东西光看名字就知道它是“最长公共前缀”的镜像问题。前缀是每个字符串的开头对齐后缀是从结尾对齐两者就差一个方向。可如果真把代码写下去你会发现很多套路不能直接平移过来比如给字符串数组排序后取首尾比较前缀场景下很好用后缀场景下却可能得出错误结果。我自己是在批量处理文件名时被这个题绊过一次后来才把暴力法、反转法、工程化修剪法完整梳理了一遍。这篇就把“最长公共字符串后缀”从定义到实现再到边界情况彻底讲透适合正在刷字符串题的人也适合写脚本处理扩展名、URL、类名时想直接抄代码的开发者。1. 先给最长公共后缀下个准确定义它不是公共子串1.1 定义和三个一眼能看懂的样例给定 n 个字符串 s1, s2, ..., sn找一个字符串 t让 t 同时是每个 si 的后缀并且 t 的长度尽可能长。这里“后缀”的意思是t 必须从某个字符串的最后一个字符往前连续取到不能跳过字符也不能不贴住末尾。看几个例子输入[abcdef, def, qqdef]最长公共后缀是def。输入[abcde, cde, qde]末尾字符分别是 e、e、e匹配再往前一位是 d、d、d继续匹配再往前是 c、c、q不匹配。所以最长公共后缀是de。输入[abc, def]末尾字符 c 和 f 不同公共后缀为空字符串。第三个例子很关键。很多初学者会想既然 abc 没有公共后缀那结果是不是 null按算法题的普遍约定最长公共后缀为空时返回而不是 null。这个约定和数据库里NULL与空字符串严格区分是两回事后面讲边界条件时会细说。1.2 公共后缀不等于公共子串也别和公共前缀混着套“公共子串”不要求贴着字符串末尾。比如xabc和abcy公共子串是abc但这两个字符串的最长公共后缀是因为前者以 c 结尾后者以 y 结尾末尾就不一样。“公共前缀”则是从头开始对齐。abcd和abef的公共前缀是ab但末尾字符 d 和 f 不同最长公共后缀也是。所以前缀和后缀虽然可以通过反转互相转化但在没有做反转操作之前代码里的索引方向完全是反的用习惯写前缀的startswith思路去处理后缀第一步就会犯方向性错误。我在实际开发里看到过一种常见的错误代码有人为了求公共后缀先把第一个字符串整个当作候选然后用每个字符串的endsWith去判断发现不匹配就把候选缩短。这个思路本身没问题可缩短短剪不断他把候选从尾部去掉一个字符结果剩下的字符串依然不是人家的后缀最后跑出来的结果不是最长公共后缀而是一个非常短的公共后缀甚至空串。1.3 这个题在真实项目里能解决什么问题不要觉得这种题只活在面试题库里后缀匹配的应用场景相当多文件扩展名归类给一批文件名找公共后缀可以判断它们是不是同一种格式比如a.tar.gz和b.tar.gz的公共后缀是.tar.gz不是.gz。URL 路径或域名公共后缀域名里的“公共后缀列表”就是个典型聚合场景example.co.uk和test.co.uk的公共后缀是.co.uk网络库经常利用这类后缀做隐私归约。日志模板提取多行日志末尾通常会带相同的时间戳或状态码提取公共后缀可以帮助压缩日志格式。在这些场景里最长公共后缀往往不是让人“肉眼都能看出来”的那一两个字符而是需要算法精确计算出来的结果。这也是为什么面试官喜欢把前缀题换成后缀题来考——换的不仅是方向还有候选人的边界意识。2. 从右往左逐字符对齐暴力解法才是大多数场景的最优解2.1 算法流程和最小长度约束最长公共后缀的长度不可能超过任何一个参与比对的字符串长度。如果有一个字符串特别短比如[abcdef, def, d]最后一个字符串只有 1 个字符那么公共后缀最多只能匹配到d。所以开局第一步是求出所有字符串长度里的最小值minLen。拿到minLen之后从右往左逐个字符比对。假设当前比较的是从末尾数第 i 个字符那么对每个字符串 s取s[s.length() - 1 - i]。如果所有字符串在这一位上的字符都相同就继续往左一旦出现某个字符不一致立刻停止。已经匹配的所有字符连起来就是最长公共后缀。这个算法看起来非常朴素但它是后缀问题的“基准答案”。面试时先把这版写出来再谈优化能让面试官立刻看到你对问题本质的理解。2.2 三种语言实现Python、Java、C先给一份 Python 版本短小直接def longest_common_suffix(strs): if not strs: return min_len min(len(s) for s in strs) match_len 0 for i in range(1, min_len 1): ch strs[0][-i] if all(s[-i] ch for s in strs): match_len i else: break return strs[0][len(strs[0]) - match_len:] if match_len else min一次循环拿到min_len然后从右往左检查。这里有一个小优化并不是所有字符串都需要完整遍历到min_len一旦某一位不等就提前break实际循环次数往往远小于min_len。Java 版本关注索引安全用charAt配合length - 1 - ipublic String longestCommonSuffix(String[] strs) { if (strs null || strs.length 0) return ; int minLen Integer.MAX_VALUE; for (String s : strs) minLen Math.min(minLen, s.length()); int matched 0; while (matched minLen) { char c strs[0].charAt(strs[0].length() - 1 - matched); for (int j 1; j strs.length; j) { String s strs[j]; if (s.charAt(s.length() - 1 - matched) ! c) { return strs[0].substring(strs[0].length() - matched); } } matched; } return strs[0].substring(strs[0].length() - matched); }注意 Java 版本里我在内部循环不匹配时直接返回而不是break外层再判断。因为一旦中间字符串不匹配前面已经匹配到的matched就是最终长度不需要再继续循环。这种写法把“提前终止”直接体现在返回语句里代码更干净。C 语言版本需要自己管字符串长度和内存#include stdio.h #include stdlib.h #include string.h #include limits.h char *longest_common_suffix(char **strs, int n) { if (n 0) return ; int min_len INT_MAX; for (int i 0; i n; i) { int len (int)strlen(strs[i]); if (len min_len) min_len len; } int matched 0; while (matched min_len) { int base_len (int)strlen(strs[0]); char c strs[0][base_len - 1 - matched]; for (int i 1; i n; i) { int len (int)strlen(strs[i]); if (strs[i][len - 1 - matched] ! c) { if (matched 0) return ; char *res (char *)malloc(matched 1); strncpy(res, strs[0] base_len - matched, matched); res[matched] \0; return res; } } matched; } if (matched 0) return ; int base_len (int)strlen(strs[0]); char *res (char *)malloc(matched 1); strncpy(res, strs[0] base_len - matched, matched); res[matched] \0; return res; }C 版本最麻烦的是返回值要么指向静态常量要么指向 malloc 出来的内存主程序用完必须 free。如果返回它指向字符串字面量不能随便 free否则会崩。我一般在接口注释里写清楚非空返回值由调用方释放。这是 C 语言实现里最容易踩的坑比算法本身更值得注意。2.3 复杂度与“为什么暴力不土”这个暴力算法的时间复杂度是 O(n × minLen)其中 n 是字符串个数minLen 是所有字符串长度的最小值。空间复杂度是 O(1)因为只用了几个整数变量和最终返回的子串。有人看到 O(n × minLen) 会觉得太慢但实际上这个问题存在一个信息论层面的下限你必须读完每个字符串末尾足够多的字符才能确定公共后缀有多长。在最坏情况下所有字符串的前 minLen 位都相同你的比较次数就是 n × minLen。任何正确算法在最坏情况下都要扫描这么多次字符所以这个“暴力”算法实际上达到了这个问题的线性下界。那为什么我还推荐在面试时先写它因为它正确、简单、不可能写错并且立刻能引出关于“能不能用现成反转函数”“能不能排序优化”的讨论。能把一个 O(n × minLen) 的代码解释清楚比背一个复杂算法然后讲不明白要有说服力得多。3. 反转字符串转化成最长公共前缀思路虽好坑也不少3.1 核心观察后缀翻转后就变成前缀假设输入是[abcde, cde, qde]全部反转后得到[edcba, edc, edq]。原来的公共后缀de反转后变成了公共前缀ed。这个对称性非常直观所以一个很自然的实现路径就是def longest_common_suffix_by_reverse(strs): if not strs: return rev_strs [s[::-1] for s in strs] # 求 rev_strs 的最长公共前缀再反转回来 prefix longest_common_prefix(rev_strs) return prefix[::-1]很多编程语言自带“求公共前缀”的工具函数或库函数比如 Python 的os.path.commonprefix所以这个方案的工程实现特别快import os def longest_common_suffix_with_os(strs): if not strs: return rev [s[::-1] for s in strs] return os.path.commonprefix(rev)[::-1]这个实现非常短适合脚本里快速完成任务。但你在刷题或面试时不要上来就写库函数因为面试官往往希望看到你自己完成“从左往右比较前缀”的过程而不是依赖运行时环境。而且os.path.commonprefix是逐字符比较的纯函数遇到多字节字符时是按字节还是按字符取决于底层实现这本身又是一个不确定因素。3.2 用“排序法”处理时容易出错的地方只要你做过最长公共前缀的题一定知道有一个“排序取首尾”的套路把所有字符串按字典序排序整体公共前缀等于排序后第一个字符串和最后一个字符串的公共前缀。这个套路搬到后缀问题时很多人的第一反应是直接对原字符串排序然后比较第一个和最后一个字符串的末尾。这个做法是有明显反例的。看这组字符串[ab, ca, cb]。整体最长公共后缀是什么ab以 b 结尾ca以 a 结尾所以末尾字符都不一样整体公共后缀是。按字典序排序后得到[ab, ca, cb]排序后的第一个是ab最后一个是cb。ab和cb的公共后缀是b排除了中间的ca结果变成了b这显然是错的。为什么前缀场景下排序法成立后缀场景下就不成立因为字典序天然按前缀组织共享前缀的字符串会靠在一起整体前缀一定包含在排序首尾的公共前缀里。但字典序不看后缀共享后缀的字符串不一定相邻排序后首尾只能代表字典序的两端不能代表所有字符串的尾部约束。正确做法是先把所有字符串反转再对反转后的字符串排序取首尾公共前缀最后反转回来。这样后缀问题就被严格转换成了前缀问题排序法重新成立。def longest_common_suffix_sorted(strs): if not strs: return rev_sorted sorted(s[::-1] for s in strs) first rev_sorted[0] last rev_sorted[-1] i 0 while i len(first) and i len(last) and first[i] last[i]: i 1 return first[:i][::-1]那这个排序法是不是更优并不是它的时间复杂度是 O(L log L)其中 L 是字符串总数反而比原来的 O(n × minLen) 更慢。排序法的价值不在于提速而在于让代码逻辑更集中先反转再用现成的公共前缀函数或排序工具。工程代码里如果字符串数量不大用这个思路可以减少手写循环逻辑正确率更高。3.3 大小写敏感与 NULL 边界在工程里的真实影响反转法还会牵出一个工程问题到底要不要区分大小写在不同运行环境里这个问题答案还不一样。比如在 MySQL 模式的 Kingbase 数据库里字符串比较默认不区分大小写ABC abc成立。而普通操作系统的文件名比较在 Windows 下通常不区分大小写在 Linux 下严格区分。你写一个longest_common_suffix函数给别人用时必须明确声明比较策略。如果区分大小写[ABC, abc]的公共后缀是。如果不区分大小写[ABC, abc]的公共后缀是ABC或abc取决于保留哪个字符串的形态。工程实现里我通常增加一个参数ignore_case或者直接复用一个ComparatorCharacter而不是在函数内部硬编码equalsIgnoreCase。这样单元测试也好写调用方也清楚行为。还有 NULL 的问题。C 语言里字符串数组可能包含空指针Java 里可能包含 null数据库场景里更常见。公共后缀函数在遇到 null 时不能盲目调用length()否则直接空指针或段错误。稳妥约定是只要数组中有一个 null就把它等价于“空字符串”那么最终结果直接返回空字符串如果题目明确说没有 null你也要在入口处做防御性校验。4. 从算法题到生产代码边界条件、中文字符与性能取舍4.1 空数组、空字符串、单字符串分别怎么约定算法题的边界条件经常决定代码能不能一把过生产代码更是如此。我建议把所有边界情况列成一张表写代码前先想清楚输入情况合理返回理由空数组[]没有可比较对象公共后缀为空只有一个字符串abcabc它本身就是自己的最长公共后缀存在一个空字符串[abc, ]空字符串的后缀只有空串两个完全相同的字符串[abc, abc]abc最大公共后缀就是本身所有字符串末尾都不一致没有匹配字符这些约定不是数学公理而是工程惯例。空数组返回什么在严谨的数学定义下是“未定义”的但如果你不返回一个明确值调用方就要自己判断很容易漏判。防御性返回空字符串是最不容易出意外的方案这个选择比“抛异常”更适合通用工具函数。4.2 中文字符和多字节编码对“长度”的干扰字符串问题一旦遇到中文字符很多语言的“长度”概念就会打架。Java 的String.length()返回 UTF-16 编码下的代码单元数量一个常见汉字占 1 个代码单元但 emoji 或生僻字可能占 2 个代码单元。Python 的len(s)返回 Unicode 代码点数量大多数汉字是 1但组合字符可能被拆成多个代码点。C 语言用strlen按字节统计一个 UTF-8 编码的汉字占 3 个字节。所以当题目或需求里出现中文你要先问一句公共后缀按“字符”对齐还是按“字节”对齐比如[你好吗, 好吗]按字符看公共后缀是好吗按 UTF-8 字节看公共后缀是好吗的 6 个字节。Python 和 Java 的[::-1]、charAt在这个例子里都能得到同一结果但如果你在 C 语言里直接用字节指针去比较遇到两个汉字中间某个字节碰巧相同就可能截出半个汉字。我的建议是通用工具函数默认按“代码点/字符”对齐而不是按字节如果确实需要按字节函数命名里一定要体现比如longest_common_suffix_bytes避免调用方误解。4.3 文件扩展名场景用 endsWith 循环修剪候选后缀实际项目中字符串数组通常不会太大但每个字符串可能很长。这时候用“候选后缀逐步缩短”的方法很好理解也容易改造成真正的业务逻辑。假设要处理一批文件名def common_suffix_for_filenames(filenames): if not filenames: return suffix filenames[0] for name in filenames[1:]: while suffix and not name.endswith(suffix): suffix suffix[1:] if not suffix: return return suffix逻辑很简单先把第一个文件名整体当作候选后缀然后用后续文件名的endswith去验证。验证不通过就把候选后缀从头部去掉一个字符继续验证。为什么是从头部去掉而不是从尾部去掉因为候选后缀必须保持是原字符串的“尾巴”如果你从尾部缩短剩下的候选就变成前缀的一部分了不再适合做后缀。比如候选abcdef如果发现某个文件名不以它结尾你期望的下一个候选是bcdef它仍然是原字符串的连续尾巴而如果从尾部去掉变成abcde它只是原串的开头用来和后缀比较就彻底失去意义了。这个做法的缺点是每次suffix suffix[1:]都创建新字符串最坏情况下时间复杂度可能到 O(L²)。但文件名数量通常不多字符串也短实际运行非常快。如果在追求极致性能的场景还是用第 2 节里从右往左逐字符比对的写法更靠谱。4.4 性能取舍能原地比较就别频繁创建子串很多语言里substring、s[::-1]、slice这类操作不一定拷贝底层数据。Java 的substring在新版本里会创建新的字符串对象旧版本可能共享底层 char 数组Python 的切片则直接创建新字符串。所以一个隐藏的性能坑是为了求一个 3 个字符的结果你可能在中间创建了无数个长度为几十、几百的临时字符串。避免方法很简单在比对阶段不要频繁截取所有比对都通过索引访问原始字符串。等确定了最终长度之后再一次性substring或构造结果。伪代码思路1. 求出最短长度 minLen 2. i 从 1 到 minLen依次比较 strs[j][len(strs[j]) - i] 3. 记录最长匹配长度 matched 4. 最后返回 strs[0] 从 (len(strs[0]) - matched) 开始的子串这样整个过程中只有最后一次会创建新字符串中间全是 O(1) 的索引访问。对于大规模数据这个差异非常明显。5. 这类题目的变体与扩展前缀、子串、后缀数组一眼看到底5.1 最长公共前缀和后缀的对称性如果你已经写好了最长公共前缀函数那最长公共后缀永远可以一行搞定def lcp(strs): # 自己写好的最长公共前缀 ... def lcs(strs): return lcp([s[::-1] for s in strs])[::-1]这个对称性看起来简单却是面试官最喜欢延伸考的点。面试官可能会问如果现在要求同时返回公共前缀和公共后缀长度能不能一次遍历完成当然可以一遍从前向后找前缀一遍从后向前找后缀两次遍历互不干扰。还有一种变体如果允许忽略大小写或者允许忽略某些通配符公共后缀函数就会变成“模糊后缀匹配”。这时候从右往左逐字符比对依然是最稳的思路你只需要在比较字符时套一层归一化函数。5.2 最长公共子串和最长公共后缀的关系字符串问题里另一道经典题是“最长公共子串”。公共后缀其实是公共子串的一个特殊情况它不仅要求子串同时在两个字符串中出现还要求它必须贴着两个字符串的末尾。用动态规划求两个字符串的最长公共子串时状态转移式是dp[i][j] dp[i-1][j-1] 1, 如果 s1[i] s2[j]这个 dp 表里如果 i 指向 s1 的末尾j 指向 s2 的末尾那dp[s1.length][s2.length]恰好就是最长公共后缀的长度。这也是一个快速解题技巧当面试官把题目改成“只求公共后缀”时你可以直接复用最长公共子串的 DP 表最后一格但更简单的做法还是从右往左逐字符比较因为公共后缀问题本身不需要二维 DP。如果面试官再追问“如果有很多字符串怎么快速找公共后缀”那就涉及分组、索引和预处理了。一个直观工程做法是把所有字符串反转后建成字典树前缀树查询公共前缀的效率很高原问题里字符串数量多、重复比较频繁时这个方案能把多次查询的总复杂度降下来。5.3 站在出题人角度看面试官换马甲是为了考察什么我在带人和模拟面试时发现最长公共后缀这道题看着简单但最容易暴露三个问题第一方向感。候选人拿到题就开始写startWith或者直接套用前缀题模板写出一个方向完全反的答案。这说明他并没有真正理解“后缀”是什么。第二边界意识。空数组、空字符串、单字符串、长度不一致、大小写敏感这些点没有主动询问而是靠测试用例去撞。实际工程里接口设计的第一步就是确认输入域。第三复杂度判断。候选人一上来就说“用后缀数组解决”显得很高级但解释不清楚为什么需要后缀数组也回答不了朴素解法为什么已经足够好。面试官更喜欢听到你先分析问题规模再给出对应方案。所以我的建议是遇到这类题先花 10 秒钟把所有边界条件和比较策略问清楚然后用最朴素的逐字符比对把代码写对再根据面试官的反应讨论优化。这比背一堆高级数据结构但方向都写反要实用得多。最后分享一个小技巧如果你是在实际项目里临时用一下直接反转字符串再调os.path.commonprefix这种库函数效率很高但如果你要把这段逻辑沉淀成团队公共代码一定要把大小写、空值、编码三个问题在注释里写清楚否则三个月后回来维护的人大概率会踩中我在第 4 节讲过的坑。 最长公共字符串后缀详解：定义、算法与工程实践
最长公共字符串后缀这东西光看名字就知道它是“最长公共前缀”的镜像问题。前缀是每个字符串的开头对齐后缀是从结尾对齐两者就差一个方向。可如果真把代码写下去你会发现很多套路不能直接平移过来比如给字符串数组排序后取首尾比较前缀场景下很好用后缀场景下却可能得出错误结果。我自己是在批量处理文件名时被这个题绊过一次后来才把暴力法、反转法、工程化修剪法完整梳理了一遍。这篇就把“最长公共字符串后缀”从定义到实现再到边界情况彻底讲透适合正在刷字符串题的人也适合写脚本处理扩展名、URL、类名时想直接抄代码的开发者。1. 先给最长公共后缀下个准确定义它不是公共子串1.1 定义和三个一眼能看懂的样例给定 n 个字符串 s1, s2, ..., sn找一个字符串 t让 t 同时是每个 si 的后缀并且 t 的长度尽可能长。这里“后缀”的意思是t 必须从某个字符串的最后一个字符往前连续取到不能跳过字符也不能不贴住末尾。看几个例子输入[abcdef, def, qqdef]最长公共后缀是def。输入[abcde, cde, qde]末尾字符分别是 e、e、e匹配再往前一位是 d、d、d继续匹配再往前是 c、c、q不匹配。所以最长公共后缀是de。输入[abc, def]末尾字符 c 和 f 不同公共后缀为空字符串。第三个例子很关键。很多初学者会想既然 abc 没有公共后缀那结果是不是 null按算法题的普遍约定最长公共后缀为空时返回而不是 null。这个约定和数据库里NULL与空字符串严格区分是两回事后面讲边界条件时会细说。1.2 公共后缀不等于公共子串也别和公共前缀混着套“公共子串”不要求贴着字符串末尾。比如xabc和abcy公共子串是abc但这两个字符串的最长公共后缀是因为前者以 c 结尾后者以 y 结尾末尾就不一样。“公共前缀”则是从头开始对齐。abcd和abef的公共前缀是ab但末尾字符 d 和 f 不同最长公共后缀也是。所以前缀和后缀虽然可以通过反转互相转化但在没有做反转操作之前代码里的索引方向完全是反的用习惯写前缀的startswith思路去处理后缀第一步就会犯方向性错误。我在实际开发里看到过一种常见的错误代码有人为了求公共后缀先把第一个字符串整个当作候选然后用每个字符串的endsWith去判断发现不匹配就把候选缩短。这个思路本身没问题可缩短短剪不断他把候选从尾部去掉一个字符结果剩下的字符串依然不是人家的后缀最后跑出来的结果不是最长公共后缀而是一个非常短的公共后缀甚至空串。1.3 这个题在真实项目里能解决什么问题不要觉得这种题只活在面试题库里后缀匹配的应用场景相当多文件扩展名归类给一批文件名找公共后缀可以判断它们是不是同一种格式比如a.tar.gz和b.tar.gz的公共后缀是.tar.gz不是.gz。URL 路径或域名公共后缀域名里的“公共后缀列表”就是个典型聚合场景example.co.uk和test.co.uk的公共后缀是.co.uk网络库经常利用这类后缀做隐私归约。日志模板提取多行日志末尾通常会带相同的时间戳或状态码提取公共后缀可以帮助压缩日志格式。在这些场景里最长公共后缀往往不是让人“肉眼都能看出来”的那一两个字符而是需要算法精确计算出来的结果。这也是为什么面试官喜欢把前缀题换成后缀题来考——换的不仅是方向还有候选人的边界意识。2. 从右往左逐字符对齐暴力解法才是大多数场景的最优解2.1 算法流程和最小长度约束最长公共后缀的长度不可能超过任何一个参与比对的字符串长度。如果有一个字符串特别短比如[abcdef, def, d]最后一个字符串只有 1 个字符那么公共后缀最多只能匹配到d。所以开局第一步是求出所有字符串长度里的最小值minLen。拿到minLen之后从右往左逐个字符比对。假设当前比较的是从末尾数第 i 个字符那么对每个字符串 s取s[s.length() - 1 - i]。如果所有字符串在这一位上的字符都相同就继续往左一旦出现某个字符不一致立刻停止。已经匹配的所有字符连起来就是最长公共后缀。这个算法看起来非常朴素但它是后缀问题的“基准答案”。面试时先把这版写出来再谈优化能让面试官立刻看到你对问题本质的理解。2.2 三种语言实现Python、Java、C先给一份 Python 版本短小直接def longest_common_suffix(strs): if not strs: return min_len min(len(s) for s in strs) match_len 0 for i in range(1, min_len 1): ch strs[0][-i] if all(s[-i] ch for s in strs): match_len i else: break return strs[0][len(strs[0]) - match_len:] if match_len else min一次循环拿到min_len然后从右往左检查。这里有一个小优化并不是所有字符串都需要完整遍历到min_len一旦某一位不等就提前break实际循环次数往往远小于min_len。Java 版本关注索引安全用charAt配合length - 1 - ipublic String longestCommonSuffix(String[] strs) { if (strs null || strs.length 0) return ; int minLen Integer.MAX_VALUE; for (String s : strs) minLen Math.min(minLen, s.length()); int matched 0; while (matched minLen) { char c strs[0].charAt(strs[0].length() - 1 - matched); for (int j 1; j strs.length; j) { String s strs[j]; if (s.charAt(s.length() - 1 - matched) ! c) { return strs[0].substring(strs[0].length() - matched); } } matched; } return strs[0].substring(strs[0].length() - matched); }注意 Java 版本里我在内部循环不匹配时直接返回而不是break外层再判断。因为一旦中间字符串不匹配前面已经匹配到的matched就是最终长度不需要再继续循环。这种写法把“提前终止”直接体现在返回语句里代码更干净。C 语言版本需要自己管字符串长度和内存#include stdio.h #include stdlib.h #include string.h #include limits.h char *longest_common_suffix(char **strs, int n) { if (n 0) return ; int min_len INT_MAX; for (int i 0; i n; i) { int len (int)strlen(strs[i]); if (len min_len) min_len len; } int matched 0; while (matched min_len) { int base_len (int)strlen(strs[0]); char c strs[0][base_len - 1 - matched]; for (int i 1; i n; i) { int len (int)strlen(strs[i]); if (strs[i][len - 1 - matched] ! c) { if (matched 0) return ; char *res (char *)malloc(matched 1); strncpy(res, strs[0] base_len - matched, matched); res[matched] \0; return res; } } matched; } if (matched 0) return ; int base_len (int)strlen(strs[0]); char *res (char *)malloc(matched 1); strncpy(res, strs[0] base_len - matched, matched); res[matched] \0; return res; }C 版本最麻烦的是返回值要么指向静态常量要么指向 malloc 出来的内存主程序用完必须 free。如果返回它指向字符串字面量不能随便 free否则会崩。我一般在接口注释里写清楚非空返回值由调用方释放。这是 C 语言实现里最容易踩的坑比算法本身更值得注意。2.3 复杂度与“为什么暴力不土”这个暴力算法的时间复杂度是 O(n × minLen)其中 n 是字符串个数minLen 是所有字符串长度的最小值。空间复杂度是 O(1)因为只用了几个整数变量和最终返回的子串。有人看到 O(n × minLen) 会觉得太慢但实际上这个问题存在一个信息论层面的下限你必须读完每个字符串末尾足够多的字符才能确定公共后缀有多长。在最坏情况下所有字符串的前 minLen 位都相同你的比较次数就是 n × minLen。任何正确算法在最坏情况下都要扫描这么多次字符所以这个“暴力”算法实际上达到了这个问题的线性下界。那为什么我还推荐在面试时先写它因为它正确、简单、不可能写错并且立刻能引出关于“能不能用现成反转函数”“能不能排序优化”的讨论。能把一个 O(n × minLen) 的代码解释清楚比背一个复杂算法然后讲不明白要有说服力得多。3. 反转字符串转化成最长公共前缀思路虽好坑也不少3.1 核心观察后缀翻转后就变成前缀假设输入是[abcde, cde, qde]全部反转后得到[edcba, edc, edq]。原来的公共后缀de反转后变成了公共前缀ed。这个对称性非常直观所以一个很自然的实现路径就是def longest_common_suffix_by_reverse(strs): if not strs: return rev_strs [s[::-1] for s in strs] # 求 rev_strs 的最长公共前缀再反转回来 prefix longest_common_prefix(rev_strs) return prefix[::-1]很多编程语言自带“求公共前缀”的工具函数或库函数比如 Python 的os.path.commonprefix所以这个方案的工程实现特别快import os def longest_common_suffix_with_os(strs): if not strs: return rev [s[::-1] for s in strs] return os.path.commonprefix(rev)[::-1]这个实现非常短适合脚本里快速完成任务。但你在刷题或面试时不要上来就写库函数因为面试官往往希望看到你自己完成“从左往右比较前缀”的过程而不是依赖运行时环境。而且os.path.commonprefix是逐字符比较的纯函数遇到多字节字符时是按字节还是按字符取决于底层实现这本身又是一个不确定因素。3.2 用“排序法”处理时容易出错的地方只要你做过最长公共前缀的题一定知道有一个“排序取首尾”的套路把所有字符串按字典序排序整体公共前缀等于排序后第一个字符串和最后一个字符串的公共前缀。这个套路搬到后缀问题时很多人的第一反应是直接对原字符串排序然后比较第一个和最后一个字符串的末尾。这个做法是有明显反例的。看这组字符串[ab, ca, cb]。整体最长公共后缀是什么ab以 b 结尾ca以 a 结尾所以末尾字符都不一样整体公共后缀是。按字典序排序后得到[ab, ca, cb]排序后的第一个是ab最后一个是cb。ab和cb的公共后缀是b排除了中间的ca结果变成了b这显然是错的。为什么前缀场景下排序法成立后缀场景下就不成立因为字典序天然按前缀组织共享前缀的字符串会靠在一起整体前缀一定包含在排序首尾的公共前缀里。但字典序不看后缀共享后缀的字符串不一定相邻排序后首尾只能代表字典序的两端不能代表所有字符串的尾部约束。正确做法是先把所有字符串反转再对反转后的字符串排序取首尾公共前缀最后反转回来。这样后缀问题就被严格转换成了前缀问题排序法重新成立。def longest_common_suffix_sorted(strs): if not strs: return rev_sorted sorted(s[::-1] for s in strs) first rev_sorted[0] last rev_sorted[-1] i 0 while i len(first) and i len(last) and first[i] last[i]: i 1 return first[:i][::-1]那这个排序法是不是更优并不是它的时间复杂度是 O(L log L)其中 L 是字符串总数反而比原来的 O(n × minLen) 更慢。排序法的价值不在于提速而在于让代码逻辑更集中先反转再用现成的公共前缀函数或排序工具。工程代码里如果字符串数量不大用这个思路可以减少手写循环逻辑正确率更高。3.3 大小写敏感与 NULL 边界在工程里的真实影响反转法还会牵出一个工程问题到底要不要区分大小写在不同运行环境里这个问题答案还不一样。比如在 MySQL 模式的 Kingbase 数据库里字符串比较默认不区分大小写ABC abc成立。而普通操作系统的文件名比较在 Windows 下通常不区分大小写在 Linux 下严格区分。你写一个longest_common_suffix函数给别人用时必须明确声明比较策略。如果区分大小写[ABC, abc]的公共后缀是。如果不区分大小写[ABC, abc]的公共后缀是ABC或abc取决于保留哪个字符串的形态。工程实现里我通常增加一个参数ignore_case或者直接复用一个ComparatorCharacter而不是在函数内部硬编码equalsIgnoreCase。这样单元测试也好写调用方也清楚行为。还有 NULL 的问题。C 语言里字符串数组可能包含空指针Java 里可能包含 null数据库场景里更常见。公共后缀函数在遇到 null 时不能盲目调用length()否则直接空指针或段错误。稳妥约定是只要数组中有一个 null就把它等价于“空字符串”那么最终结果直接返回空字符串如果题目明确说没有 null你也要在入口处做防御性校验。4. 从算法题到生产代码边界条件、中文字符与性能取舍4.1 空数组、空字符串、单字符串分别怎么约定算法题的边界条件经常决定代码能不能一把过生产代码更是如此。我建议把所有边界情况列成一张表写代码前先想清楚输入情况合理返回理由空数组[]没有可比较对象公共后缀为空只有一个字符串abcabc它本身就是自己的最长公共后缀存在一个空字符串[abc, ]空字符串的后缀只有空串两个完全相同的字符串[abc, abc]abc最大公共后缀就是本身所有字符串末尾都不一致没有匹配字符这些约定不是数学公理而是工程惯例。空数组返回什么在严谨的数学定义下是“未定义”的但如果你不返回一个明确值调用方就要自己判断很容易漏判。防御性返回空字符串是最不容易出意外的方案这个选择比“抛异常”更适合通用工具函数。4.2 中文字符和多字节编码对“长度”的干扰字符串问题一旦遇到中文字符很多语言的“长度”概念就会打架。Java 的String.length()返回 UTF-16 编码下的代码单元数量一个常见汉字占 1 个代码单元但 emoji 或生僻字可能占 2 个代码单元。Python 的len(s)返回 Unicode 代码点数量大多数汉字是 1但组合字符可能被拆成多个代码点。C 语言用strlen按字节统计一个 UTF-8 编码的汉字占 3 个字节。所以当题目或需求里出现中文你要先问一句公共后缀按“字符”对齐还是按“字节”对齐比如[你好吗, 好吗]按字符看公共后缀是好吗按 UTF-8 字节看公共后缀是好吗的 6 个字节。Python 和 Java 的[::-1]、charAt在这个例子里都能得到同一结果但如果你在 C 语言里直接用字节指针去比较遇到两个汉字中间某个字节碰巧相同就可能截出半个汉字。我的建议是通用工具函数默认按“代码点/字符”对齐而不是按字节如果确实需要按字节函数命名里一定要体现比如longest_common_suffix_bytes避免调用方误解。4.3 文件扩展名场景用 endsWith 循环修剪候选后缀实际项目中字符串数组通常不会太大但每个字符串可能很长。这时候用“候选后缀逐步缩短”的方法很好理解也容易改造成真正的业务逻辑。假设要处理一批文件名def common_suffix_for_filenames(filenames): if not filenames: return suffix filenames[0] for name in filenames[1:]: while suffix and not name.endswith(suffix): suffix suffix[1:] if not suffix: return return suffix逻辑很简单先把第一个文件名整体当作候选后缀然后用后续文件名的endswith去验证。验证不通过就把候选后缀从头部去掉一个字符继续验证。为什么是从头部去掉而不是从尾部去掉因为候选后缀必须保持是原字符串的“尾巴”如果你从尾部缩短剩下的候选就变成前缀的一部分了不再适合做后缀。比如候选abcdef如果发现某个文件名不以它结尾你期望的下一个候选是bcdef它仍然是原字符串的连续尾巴而如果从尾部去掉变成abcde它只是原串的开头用来和后缀比较就彻底失去意义了。这个做法的缺点是每次suffix suffix[1:]都创建新字符串最坏情况下时间复杂度可能到 O(L²)。但文件名数量通常不多字符串也短实际运行非常快。如果在追求极致性能的场景还是用第 2 节里从右往左逐字符比对的写法更靠谱。4.4 性能取舍能原地比较就别频繁创建子串很多语言里substring、s[::-1]、slice这类操作不一定拷贝底层数据。Java 的substring在新版本里会创建新的字符串对象旧版本可能共享底层 char 数组Python 的切片则直接创建新字符串。所以一个隐藏的性能坑是为了求一个 3 个字符的结果你可能在中间创建了无数个长度为几十、几百的临时字符串。避免方法很简单在比对阶段不要频繁截取所有比对都通过索引访问原始字符串。等确定了最终长度之后再一次性substring或构造结果。伪代码思路1. 求出最短长度 minLen 2. i 从 1 到 minLen依次比较 strs[j][len(strs[j]) - i] 3. 记录最长匹配长度 matched 4. 最后返回 strs[0] 从 (len(strs[0]) - matched) 开始的子串这样整个过程中只有最后一次会创建新字符串中间全是 O(1) 的索引访问。对于大规模数据这个差异非常明显。5. 这类题目的变体与扩展前缀、子串、后缀数组一眼看到底5.1 最长公共前缀和后缀的对称性如果你已经写好了最长公共前缀函数那最长公共后缀永远可以一行搞定def lcp(strs): # 自己写好的最长公共前缀 ... def lcs(strs): return lcp([s[::-1] for s in strs])[::-1]这个对称性看起来简单却是面试官最喜欢延伸考的点。面试官可能会问如果现在要求同时返回公共前缀和公共后缀长度能不能一次遍历完成当然可以一遍从前向后找前缀一遍从后向前找后缀两次遍历互不干扰。还有一种变体如果允许忽略大小写或者允许忽略某些通配符公共后缀函数就会变成“模糊后缀匹配”。这时候从右往左逐字符比对依然是最稳的思路你只需要在比较字符时套一层归一化函数。5.2 最长公共子串和最长公共后缀的关系字符串问题里另一道经典题是“最长公共子串”。公共后缀其实是公共子串的一个特殊情况它不仅要求子串同时在两个字符串中出现还要求它必须贴着两个字符串的末尾。用动态规划求两个字符串的最长公共子串时状态转移式是dp[i][j] dp[i-1][j-1] 1, 如果 s1[i] s2[j]这个 dp 表里如果 i 指向 s1 的末尾j 指向 s2 的末尾那dp[s1.length][s2.length]恰好就是最长公共后缀的长度。这也是一个快速解题技巧当面试官把题目改成“只求公共后缀”时你可以直接复用最长公共子串的 DP 表最后一格但更简单的做法还是从右往左逐字符比较因为公共后缀问题本身不需要二维 DP。如果面试官再追问“如果有很多字符串怎么快速找公共后缀”那就涉及分组、索引和预处理了。一个直观工程做法是把所有字符串反转后建成字典树前缀树查询公共前缀的效率很高原问题里字符串数量多、重复比较频繁时这个方案能把多次查询的总复杂度降下来。5.3 站在出题人角度看面试官换马甲是为了考察什么我在带人和模拟面试时发现最长公共后缀这道题看着简单但最容易暴露三个问题第一方向感。候选人拿到题就开始写startWith或者直接套用前缀题模板写出一个方向完全反的答案。这说明他并没有真正理解“后缀”是什么。第二边界意识。空数组、空字符串、单字符串、长度不一致、大小写敏感这些点没有主动询问而是靠测试用例去撞。实际工程里接口设计的第一步就是确认输入域。第三复杂度判断。候选人一上来就说“用后缀数组解决”显得很高级但解释不清楚为什么需要后缀数组也回答不了朴素解法为什么已经足够好。面试官更喜欢听到你先分析问题规模再给出对应方案。所以我的建议是遇到这类题先花 10 秒钟把所有边界条件和比较策略问清楚然后用最朴素的逐字符比对把代码写对再根据面试官的反应讨论优化。这比背一堆高级数据结构但方向都写反要实用得多。最后分享一个小技巧如果你是在实际项目里临时用一下直接反转字符串再调os.path.commonprefix这种库函数效率很高但如果你要把这段逻辑沉淀成团队公共代码一定要把大小写、空值、编码三个问题在注释里写清楚否则三个月后回来维护的人大概率会踩中我在第 4 节讲过的坑。