刷 LeetCode 的时间长了你会发现一个很有意思的现象有些题看名字像是在考某个特定的数据结构或字符串技巧结果点进去一读题发现真正卡住你的反而是数学。字符串的最大公因子这道题就是一个典型。题目标签里挂着“字符串”实际上核心考点却是最大公约数GCD这名字一出来很多人第一反应是“又得去翻欧几里得算法了”但真刷进去就会发现这道题对数学的要求非常克制真正考验的是两件事一是你能不能把一个字符串的重复周期问题转化为整数的整除问题二是你能不能在所有可能的候选解里快速拍板“不用试了长度就是它”。我在刷题群里见过不少人被这道题绕晕原因倒不是题目难而是切入角度不对。有人一上来就想着怎么暴力枚举所有可能的前缀然后一个一个去模除验证代码写了一大堆跑起来倒是能过但总感觉没抓到重点。也有人一上来就盯着“最大公因子”这几个字直接把字符串长度求个 GCD 就算完事然后提交发现有的用例过不去就开始怀疑人生。这篇文章我就把这道题从最底层的数学原理到最终的代码实现再到容易踩的边界坑一条线完整拆给你看。先说清楚这道题是干什么的。题目会给两个非空字符串比如说ABCABC和ABC要求找出一个最长的字符串使得这个字符串分别重复若干次之后能精确拼出给定的两个字符串。在这个例子里答案就是ABC。顺着这个定义往下想如果两个字符串本身没有任何公共的重复单元那答案就是空字符串。注意这里有一个隐含的条件很容易被忽略所谓的“重复若干次”次数必须是正整数也就是说任何一个字符串自身一定是自己的因子因为它可以看作“重复一次”得到的结果。理解了这个前提后面很多推导才会顺。1. 这道题最反直觉的地方它考的是数学不是字符串1.1 先读懂题目到底在问什么含暴力思路我们先把题目还原成最朴素的问题给定字符串str1和str2要找一个最长的字符串X使得存在正整数i和j满足X重复i次等于str1X重复j次等于str2。注意这里的顺序str1和str2谁重复的次数多并不影响答案我们要找的这个X必须同时是两个字符串的“完整拼图块”。换句话说X的长度同时整除str1.length()和str2.length()。这一点是整道题的入手点。最笨的办法也就是暴力法思路很直接从长字符串的前缀里从长到短依次尝试每一个可能的长度看看这个长度的前缀是不是同时满足“能被str1整除”和“能被str2整除”如果满足再验证它重复若干次之后是不是精确等于两个字符串。这个办法的时间复杂度在最坏情况下是 O(n²) 级别因为每个长度你都要做一次字符串拼接和比较对于 LeetCode 上这种短字符串来说其实也能过但这道题显然有更优的做法。不过先别急着优化。暴力法的价值在于它强迫你理解“前缀”和“倍数”这两个核心概念。你要找的X必然是str1的前缀同时也必然是str2的前缀。如果不是两个字符串的公共前缀那就不用看了直接返回空字符串。这个性质看似废话却是正确性的第一道防线。1.2 为什么暴力法能过但没意思暴力法能过是因为 LeetCode 给的数据范围很温柔字符串长度撑死了也就 1000。但你刷题不能只为了过你得想清楚暴力的瓶颈在哪。瓶颈就在于你枚举了太多不必要的长度。假设str1长度是 12str2长度是 8按暴力法的逻辑你会从 12 开始往下试11、10、9... 这些长度全都试一遍。但仔细一想一个长度如果都不能同时整除 12 和 8那它连“因子”都不是根本不可能成为公共因子字符串的长度。所以你真正需要关注的其实只有同时整除两个字符串长度的那些长度也就是12和8的公共因子。这就把问题从一个“字符串逐位匹配”的问题降维成了一个“整数找公约数”的问题。12 和 8 的最大公约数是 4而 4 的因子分别是 1、2、4。理论上答案只可能从这几个长度里出。但这里要小心一点所有公共因子长度的前缀里最长的那个就是最大公因子字符串的候选吗不一定。直观上我们肯定希望“长度越长字符串越大”但字符串之间的“因子”关系并不是按长度单调的。不过在这道题里思路可以简化如果存在一个长度为d的公共因子字符串X那它重复k次得到的长度是k*d如果k*d也同时整除str1和str2的长度那X重复k次得到的新字符串长度更长也依然是公共因子字符串。这就意味着如果你能找到一个长度最长的公共因子字符串那它就是答案而长度最长的公共因子正好就是两个字符串长度的最大公约数。所以这道题的最优解核心步骤其实只有两步先求出两个字符串长度的最大公约数g然后判断长度为g的前缀是不是有效答案。是就返回不是就返回空。2. 最大公因子字符串与 Gcd 的长度关系核心突破点2.1 从“重复单元”到“整除关系”的形式化要把这道题讲透必须把“字符串的重复”和“整数的整除”这两件事之间的关系说明白。假设最终答案是Xstr1 X X ... X一共m次str2 X X ... X一共n次。那很明显len(str1) m * len(X)len(str2) n * len(X)。也就是说len(X)同时整除len(str1)和len(str2)于是len(X)是len(str1)和len(str2)的公共因子。公共因子里最大的那个是两者的最大公约数g gcd(len(str1), len(str2))。现在问题来了如果长度为len(X)的因子存在那长度为g的因子一定存在吗答案是肯定的而且这个结论几乎不用枚举。你想想X重复m次得到str1那str1的周期就是len(X)。现在g是len(X)的倍数因为len(X)整除两个长度而g是最大公约数所以len(X)也整除g... 等等这里要反过来理一下。更准确地说因为len(X)同时整除len(str1)和len(str2)所以len(X)一定整除g这是最大公约数的基本性质任何公因子都整除最大公因子。那么str1的前g个字符这个前缀长度是g它是不是一个公共因子字符串呢这里需要一点小推导str1可以看作X重复m次那么由于g是len(X)的整数倍str1当然也可以看作(X 重复 g / len(X) 次)这个新字符串重复m * len(X) / g次。同理str2也可以看作同一个新字符串重复整数次。也就是说str1的前g个字符恰好就是“X重复g / len(X)次”得到的结果它同样能拼出str2。这个推理想明白之后你会发现一个更强的结论如果存在任何一个公共因子字符串那么长度为两个字符串长度最大公约数的前缀一定也是公共因子字符串而且它一定比原来那个公共因子字符串更长或等长。所以答案要么是长度为g的前缀要么就没有任何非空答案。2.2 gcd(lenS, lenT)就是候选长度的原因需要一个扎实的证明上面这段推理可能有人觉得抽象我换个更直观的说法。把str1想象成一堵墙它的长度是astr2想象成另一堵墙长度是b。现在有一块砖X长度是d它能恰好铺满两堵墙这对应d整除a和b。现在你拿两堵墙长度的最大公约数g出来长度是g的一块“大砖”它能铺满这两堵墙吗数学上可以证明能。为什么因为g是a和b线性组合的最小正整数结果也就是贝祖定理的通俗版本所以g一定可以被拆成若干个d拼起来。既然每块小砖都能恰好铺满墙那用几块小砖拼成的大砖当然也照样能铺满墙。换句话说只要存在任意一个公共因子字符串长度为g的前缀就一定是答案如果长度为g的前缀本身不能满足“整除后精确相等”的条件那就说明压根不存在任何非空公共因子字符串。这个结论非常强它直接把你需要验证的候选长度从“所有公共因子”压缩到一个数。而最大公约数本身可以用欧几里得算法在 O(log min(a, b)) 时间内算出来这就是这道题能做到非常快的原因。当然光证明“长度是g”还不够你还要验证这个前缀是不是真的“能干这活”。为什么因为长度满足整除关系只能说明数量上对得上不能说明内容上对得上。举个简单的反例str1 ABAABAstr2 ABA字符串长度分别是 6 和 3最大公约数是 3长度为 3 的前缀是ABA这个验证是能过的答案就是ABA。但换一个例子str1 ABABABstr2 ABAB长度分别是 6 和 4最大公约数是 2长度为 2 的前缀是AB验证通过答案也是AB。这两个例子里“长度整除”和“内容匹配”恰好一致。但是再看str1 ABABABstr2 ABC长度是 6 和 3最大公约数是 3长度为 3 的前缀是ABA。你拿ABA去重复ABAABA拼不出str2 ABC于是正确答案是空字符串。这里长度的整除关系成立了3 整除 63 整除 3但内容对不上所以必须有一个额外的验证步骤。这个验证步骤在代码里通常有两种写法一种是拿长度为g的前缀去重复对应次数然后比较另一种更简洁我后面会讲。3. 正确性验证与边界用例光有长度远远不够3.1 为什么必须拼接比对很多第一次做这道题的人在算出g gcd(len1, len2)之后直接返回str1[:g]结果挂了几个用例就开始各种怀疑自己的 GCD 写错了。其实没写错就是漏了“内容验证”。为什么必须验证因为“长度是公共因子”只是必要条件不是充分条件。你要的是这个前缀重复若干次之后能精确还原成两个原始字符串而不是仅仅长度能整除。这就像你想用一批砖块铺两间不同尺寸的房间砖块的尺寸能整除两间房间的长宽只是前提你还要保证铺出来的图案是你想要的图案。具体的验证写法也方便假设我取candidate str1[:g]然后计算str1应该由len1 / g个candidate拼成str2应该由len2 / g个candidate拼成。如果这两次拼接的结果和原字符串完全一致那candidate就是答案否则就是没有答案返回空字符串。这时候你再回头看暴力法为什么不优雅因为它花了大量时间去验证那些长度都不可能整除的候选。而用 GCD 定位之后你只验证一个候选效率自然高得多。3.2 一个更省事的验证技巧实际上还有一个更简单、代码更短的验证方式而且很多高效题解都是这么写的先判断str1 str2是否等于str2 str1如果不等直接返回空字符串如果相等答案就是str1[:gcd(len1, len2)]。这个技巧第一次见到时可能会觉得“这什么东西凭什么”我来解释一下它的原理你用好了可以大幅减少出 bug 的概率。先想这么一件事如果str1和str2存在一个非空的公共因子字符串X那么str1 X * mstr2 X * n于是str1 str2 X * (m n)str2 str1 X * (n m)这俩字符串都是由X重复mn次得到的所以必然相等。反过来如果str1 str2 str2 str1那能不能推出“存在公共因子字符串”呢这里需要用到一个字符串理论的结论如果两个字符串a和b满足a b b a那么它们都“由同一个字符串重复若干次得到”。这个结论的证明思路是如果a b b a说明a和b“可交换”而可交换的字符串必然存在一个共同的周期。严谨的证明会用到 Fine 和 Wilf 的周期定理但在刷题场景下你只需要记住这个判定条件就行。所以这个验证技巧的本质是拼接相等性检查一次性把所有内容对齐问题都解决了。它比“先取前缀再重复比较”更简洁也避免了那种“长度对了但内容不对”的回车式判断。当然用str1 str2 str2 str1有个小代价就是要额外申请两个拼接字符串的内存对于 LeetCode 这种长度 1000 以内的题这点内存开销根本不值一提。但如果你在面试里用这个技巧面试官追问“为什么拼接相等就够了”你得能说出上面那段原理而不是说“试出来的”。把两个方案的优缺点放在一起看验证方案代码量需要理解的前提风险点取 GCD 长度前缀分别重复后与原串比较稍多理解g为什么是候选长度容易漏掉内容不一致的情况先判str1 str2 str2 str1再取前缀短理解可交换字符串的周期性需要额外内存但本题可忽略4. 代码实现从暴力到优化的演进4.1 基础版用 GCD 长度定位候选并验证先给出最直接、最不容易出错的写法适合面试时先说清楚思路再动手的情况。以 Python 为例def gcd(a, b): while b: a, b b, a % b return a def gcdOfStrings(str1: str, str2: str) - str: len1, len2 len(str1), len(str2) g gcd(len1, len2) candidate str1[:g] if candidate * (len1 // g) str1 and candidate * (len2 // g) str2: return candidate return 这段代码的逻辑非常朴实算出 GCD 长度取前缀然后用“重复若干次”的方式验证是否精确还原两个字符串。优点是每一个步骤的意图都很直白不容易因为“炫技”而埋 bug。缺点是如果你不理解为什么candidate会用str1[:g]而不是别的字符串你在面试时很容易被追问到哑口无言。复杂度方面欧几里得算法是 O(log min(len1, len2))验证阶段每次拼接和比较的复杂度是 O(len1 len2)整体是线性的已经足够好了。4.2 简化版先判拼接再取 GCD 前缀更常见的简洁题解长这样def gcdOfStrings(str1: str, str2: str) - str: if str1 str2 ! str2 str1: return from math import gcd return str1[:gcd(len(str1), len(str2))]Python 的math模块直接提供了gcd连欧几里得都不用自己写。前面两步等于把“内容对齐”和“长度候选”分开处理判断顺序清晰不容易漏。如果你写 JavaScript逻辑完全一样function gcd(a, b) { while (b) { [a, b] [b, a % b]; } return a; } var gcdOfStrings function(str1, str2) { if (str1 str2 ! str2 str1) return ; return str1.slice(0, gcd(str1.length, str2.length)); };注意 JavaScript 的字符串比较用!或者!都行但拼接时不要忘了加括号否则的优先级问题可能会让你 debug 很久。另外slice和substring在这个场景下效果一样但slice语义更清晰。4.3 一个大坑长度相同但内容不同的字符串还有一种非常刁钻的边界情况str1和str2长度完全相同。比如str1 ABCstr2 ABC那最大公约数就是 3前缀就是ABC直接返回没问题。但如果str1 ABCstr2 ABD两个字符串长度都是 3GCD 也是 3前缀是ABC你拿ABC去验证发现拼不出ABD于是返回空字符串。如果你用简化版第一步str1 str2 ABCABDstr2 str1 ABDABC明显不相等直接返回空更干脆。从这个例子里你也能看出来为什么“先判拼接相等”这个方案在边界情况下更安全因为它把“长度关系”和“内容关系”同时做了校验不会出现“长度对了但内容不对”却还硬返回前缀的情况。4.4 再给一个 C 的参考写法C 的标准库也自带gcd在numeric头文件里C17 之后可用。写起来是这样#include numeric #include string using namespace std; class Solution { public: string gcdOfStrings(string str1, string str2) { if (str1 str2 ! str2 str1) return ; return str1.substr(0, gcd(str1.size(), str2.size())); } };这里有一个细节gcd接受的参数类型是整数str.size()返回的是size_t在某些编译器下可能因为无符号整数的隐式转换出现警告但通常不影响结果。稳妥一点可以强转成int再传不过 LeetCode 的环境没那么严格直接写也没问题。5. 刷完这道题能带走的东西题目之外的算法思维5.1 “两个串拼接相等”这个判断条件的复用价值这道题里最值得记住的技巧其实是str1 str2 str2 str1这个判定方式。它几乎是字符串周期类问题的“万金油”。什么叫周期类问题比如给定一个字符串让你判断它是不是由某个子串重复多次得到的。最常见的解法是“字符串加自身再找子串”的技巧也就是s s里去掉首尾字符后查找是否包含s。但如果你要判断的是“两个字符串是否有公共周期”用拼接相等性判断会更直接。再举个例子有些变体题会让你判断一个字符串经过若干次左移或右移之后能否变成另一个字符串。这种题的经典解法是把一个字符串拼两次然后看另一个字符串是不是它的子串。背后的道理其实和这道题是相通的当你把字符串“复制一份接在后面”你实际上构造了一个“包含所有可能的循环位移”的超级串。这种“用拼接代替枚举”的思路在字符串题里非常常见刷多了你会发现它就是个套路。5.2 GCD 不只是数论题专用也是字符串题的剪枝利器很多人学 GCD 是在数学题里学的比如“求两个数的最大公约数”“分苹果问题”“瓷砖铺地问题”到了字符串题里就想不到用它。这道题最妙的点在于它把“字符串长度”这个离散的数值当作研究对象而“因子”这个概念天然适合用 GCD 来聚合。以后你遇到类似的问题比如“求两个字符串的最长重复前缀”“求两个字符串的公共周期串”都可以沿用这个思路先把长度关系用 GCD 收敛到一个候选值再去验证内容。这种“先算长度再验内容”的分步策略避免了在字符串空间里盲目搜索。我自己的体会是算法题里很多高效的解法都不是“一步到位的魔法”而是“两个简单思维的叠加”。这道题的第一层思维是“公共因子字符串的长度必须是两个字符串长度的公共因子”第二层思维是“内容验证用拼接相等性解决”。每一层拆开看都很简单合在一起就是一个简洁又正确的题解。5.3 几个容易让人犹豫的思考点我见过不少人在评论区问为什么不能直接取两个字符串的最小公倍数LCM长度的前缀问这个问题的思路大概是两个字符串的最小公倍数长度可能对应它们各自拼接若干次之后第一次相同的位置。比如str1 ABstr2 ABAB最小公倍数是 4str1拼两次是ABABstr2拼一次也是ABAB。但这只能说明这两个字符串在某次拼接后“长度相等”不能说明它们有公共因子。实际上最小公倍数对应的字符串是“两个字符串拼接结果相等时的最短长度”而不是“能同时整除两者的最大的重复单元”。所以这道题要找的答案跟最大公约数相关跟最小公倍数关系不大。还有人会在递归版本和迭代版本之间纠结。其实这道题根本不需要递归。最大公约数用标准库或者递归写法都能快速求出不需要额外引入更复杂的逻辑。递归的写法虽然看起来简洁但理解成本更高面试时不一定加分。6. 常见追问与题目扩展6.1 如果要求返回所有公共因子字符串把这道题改一下不要求“最大”而是要求返回“所有公共因子字符串”。那怎么办思路也不难。先利用这道题的核心结论如果存在公共因子字符串那么长度为g gcd(len1, len2)的前缀一定是其中一个而且是最大那个。其他所有公共因子字符串长度一定是g的因子而且都应该是这个最大公共因子字符串的“重复子前缀”。所以你可以遍历g的所有因子d判断长度为d的前缀是否满足candidate * (len1 // d) str1且candidate * (len2 // d) str2满足就加入结果列表。这里有个小优化点因为所有公共因子字符串都是由同一个“基串”重复若干次得到的所以可以直接在最大公共因子子串上做因子长度的前缀截取不需要从str1原始串上反复截取。这算是顺着这道题思路的合理延伸。6.2 同一套思路的变体题字符串的“整除关系”其实在很多题里都有影子。比如判断一个字符串是否完全由另一个字符串重复多次组成s是否是t的重复。寻找两个字符串的最长公共前缀同时要求这个前缀是某个重复单元。在字符串数组中寻找所有“同周期”的字符串分组比如ABAB和ABABAB有相同的周期基AB。这些题目看起来各不相同但核心推导路径几乎一样先用长度的整除关系缩小范围再用字符串拼接比较内容。掌握了这道题再碰到这类变体你的第一反应就会是“这题最多只是把字符串换成了数组或者把两个字符串换成了多个字符串核心还是找公共的重复单元”。6.3 字符串周期检测和这道题的关系再往深了说这道题还隐含着字符串周期的一个经典判定一个字符串s是否有周期p当且仅当p整除len(s)且s[:len(s) - p] s[p:]。你把str1和str2都换成同一个字符串s这道题就退化成了“判断s的最大周期因子是什么”。这类周期检测在线性时间复杂度内可以用 KMP 算法的前缀函数来做但通常刷题时用拼接相等性已经足够。如果你以后遇到更苛刻的数据范围——比如字符串长度达到 10 的 6 次方——那时候再考虑 KMP 也不迟。7. 实际刷题时的几个心得体会这道题在 LeetCode 上属于“简单到中等”的边缘但它的通过率不算特别高原因就在于很多人把题想复杂了或者想简单了就是没有人认真推导“为什么答案是长度 GCD 的前缀”。我在实际刷题复盘时总结出三个值得注意的点分享给大家。第一个点一定要区分“长度上的因子”和“字符串上的因子”。长度上的因子只需要做整数除法字符串上的因子还得做内容比对。很多人挂在“长度对了但内容不对”这种 case 上就是因为默认了长度因子就是字符串因子。做任何算法题都要警惕“必要条件被当成充分条件”的陷阱。第二个点写代码前先把小例子手跑一遍。比如str1 ABABABstr2 ABAB你会很快发现答案是AB。再跑一个str1 LEETstr2 CODE你会发现拼接不相等答案是空。这两个例子基本覆盖了这道题的全部逻辑分支。刷题时养成先跑小例子的习惯可以避免很多“思路看着对一提交就 WA”的尴尬。第三个点在面试里把数学部分的推导讲清楚比把代码写出来更重要。你直接写出str1 str2 str2 str1这种代码面试官可能觉得你是背题。但如果你从“重复单元 → 长度整除 → 公共因子长度 → 最大公约数 → 内容校验”这条逻辑链讲下来最后再给代码面试官就会觉得你是真正理解这道题。我自己复盘时最大的收获正是把这套逻辑链完整地组织起来而不只是记住一两个边界条件。最后说一个很多人没注意到的细节这个题在中文语境下叫“字符串的最大公因子”但如果你去看英文原文是Greatest Common Divisor of Strings直译就是“字符串的最大公约数”。这个命名本身就是一个提示它明确告诉你这道题的正确打开方式是把字符串看成“由某个基串重复扩展而成”的数然后用数论的视角去找最大公约数。审题时如果能从英文名里获取到这个引导思路会顺很多。刷算法题有时候差的不是代码能力而是“换个角度看问题”的范式转换能力。这道题就是一次特别好的思维体操从字符串的重复性出发把它还原成整数之间的关系再用最大公约数锁定答案。明白这一点之后你再遇到类似的“看似字符串、实则数学”的题就不会再慌。
