力扣459与1768：KMP字符串匹配与双指针模拟刷题实战

1. 两道题的整体定位与刷题思路

先说结论：今天这组合我挺满意。459和1768，一个考的是字符串交替合并的模拟能力，另一个考的是对字符串匹配底层原理的理解。难度上，1768属于不折不扣的"力扣简单题"，459虽然也被标成简单题，但如果不熟悉KMP这类的字符串匹配算法，第一次接触时很容易卡住。两题一前一后刷，正好可以从"会做"过渡到"知道为什么能这么做"。

我平时刷题有个习惯：同一批题里尽量让题型有点差异化。热身题负责保持手感，核心题负责深挖某个知识点。1768就是这个热身题，五六分钟写完，主要用来进入状态；459则是今天的重点，值得认真推导一遍，把字符串匹配里的前缀函数彻底弄明白。

有个细节需要先提一下：459题在LeetCode上属于"字符串"分类，经典解法有两种，一种是用KMP求最长公共前后缀，另一种是构造s + s再去头去尾后用查找函数判断子串是否存在。后一种写法非常短，几行代码就结束了，但如果不知道它背后的数学推导，面试时一旦被追问就很容易露馅。所以这篇记录里我会把两种解法都展开讲，尤其是那个几行代码版本的证明逻辑，一定要吃透。

再聊聊刷题节奏。很多新手喜欢按题号从1开始一路往下刷，我不太推荐这种方式。力扣热题100和力扣刷题指南这类整理好的题目列表，其实更适合用来安排每日计划，因为它们是按知识点和目标梯度筛选过的。459和1768这两题，都属于在字符串题目中具有"样板价值"的题，一个练模拟、一个练原理，值得专门写进记录。

2. 1768交替合并字符串的快速实现

2.1 题目描述与直观思路

题目要求很好懂：给你两个字符串word1和word2，把两个字符串按索引从小到大的顺序，依次交替取字符，合并成一个新字符串。比如word1 = "abc"，word2 = "pqr"，合并结果就是"apbqcr"。如果一个字符串比另一个长，那么长的那个字符串剩余的部分直接接到结果末尾。举例而言，word1 = "ab"，word2 = "pqrs"，合并结果是"apbqrs"。

这个题核心就一句话：用两个指针分别指向两个字符串的起始位置，只要任一指针还没走到末尾，就轮流取字符。处理完较短的公共长度后，把较长字符串剩下的部分一次性追加进去。

很多资料里讲这道题会提到"双指针"这个概念，这里就是最朴素的用法。两个指针各自维护当前读取位置，步长固定为1，直到越界为止。

2.2 Python实现与复杂度

我当天的代码是这样的：

class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: i, j = 0, 0 res = [] while i < len(word1) or j < len(word2): if i < len(word1): res.append(word1[i]) i += 1 if j < len(word2): res.append(word2[j]) j += 1 return "".join(res)

这里有一个值得注意的细节：我没有直接用字符串拼接，而是先用列表收集字符，最后再用"".join(res)一次性转成字符串。原因是Python里的字符串是不可变对象，如果不断执行res += word1[i]这样的操作，每次都会生成一个新的字符串，实现上是需要重新分配内存的。虽然这道题输入规模很小，看不出来性能差异，但养成用列表收集再join的习惯，在刷更复杂的字符串题时能少踩不少坑。

复杂度这块很简单：两个指针合计最多移动len(word1) + len(word2)次，时间复杂度O(m+n)，空间复杂度O(m+n)（结果字符串本身占用的空间）。如果把结果字符串的空间忽略不计，额外只用了两个指针级别的辅助空间，那可以认为空间复杂度是O(1)，但面试时建议不要把返回值的空间算进去，直接说额外空间O(1)即可。

2.3 边界条件与写法变体

这道题的边界条件主要是三个：两个字符串都是空串；其中一个为空串；两个字符串长度差很多。处理起来都不难，因为while循环条件用的是or，天然兼容了这些边界情况。

还有一个常见的变体写法，是先把公共长度部分合并完，再单独处理剩余部分：

class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: m, n = len(word1), len(word2) i = 0 res = [] while i < min(m, n): res.append(word1[i]) res.append(word2[i]) i += 1 if i < m: res.append(word1[i:]) if i < n: res.append(word2[i:]) return "".join(res)

两种写法本质上是同一个思路，区别只在于循环里控制条件的写法。我更喜欢第一种写法，因为它在"两个指针轮流取字符"的逻辑上更统一，一旦将来遇到"三个字符串交替合并"之类的变体题，把循环体扩展起来更顺手。第二种写法则更直观地体现了"先合并公共部分，再处理剩余部分"的思路。各有各的清晰点，选一个顺手的就好。

注意：假如面试官追问"能不能不用辅助列表，直接构造结果字符串"，在Python里用res = ""然后不断+=也是可以的，但这只是对这道小规模简单题可行。真正到了大字符串拼接场景，列表+join是更稳妥的做法。

2.4 为什么简单题也要认真写

1768这道题被归为"力扣简单题"没有任何问题，但它并不是完全没有训练价值。它训练的是对索引和边界的敏感度。很多人刷简单题时容易稀里糊涂一遍过，但换个输入顺序就会写错，原因就是没有认真去理解条件为什么这样写。我在刷题记录里习惯把这题标记为"基础双指针模拟"，不是为了凑数，而是为了让自己在一道题上确认：能够一遍写对，且能解释清楚每个条件的作用。

3. 459重复的子字符串的原理与解法

3.1 题目在问什么

459题的要求也不长：给定一个非空字符串s，检查它是否可以通过由它的一个子串重复多次构成。比如"abab"可以由"ab"重复两次组成，结果是true；"aba"就不能由某个子串重复构成，结果是false。"abcabcabcabc"可以由"abc"重复四次组成，也可以由"abcabc"重复两次组成，这些都是合法的。

这个题目背景放在LeetCode的简单题里算是有一定思维量的。因为它考的不是你能不能想到某个直观解法，而是你能不能把"重复构成"这个条件转化成数学判断。最直观的枚举法当然能做：枚举可能的子串长度，验证这个长度能否整除原串长度，然后再逐段比对。但这样的时间复杂度是O(n^2)，不是最优解。

其实看到"重复多次构成"这句话，就应该敏感地联想到字符串匹配中的前缀函数。这也是为什么说这题虽然标记为简单，但很适合作为学习KMP的入门应用题。

3.2 解法一：KMP前缀函数法

先交代清楚KMP中前缀函数的基本概念：对于一个字符串，它的前缀函数（也称next数组或部分匹配表）中，第i个位置存储的值表示"该位置之前的子串中，最长的相同真前缀和真后缀的长度"。注意这里是真前缀和真后缀，也就是不能取整个子串本身。

以"abab"为例，手动算一遍最长公共前后缀长度：

• 下标0的字符是'a'，前缀函数值等于0。
• 下标1的字符是'b'，子串为"ab"，最长公共前后缀长度是0，因为"a"和"b"不相等。
• 下标2的字符是'a'，子串为"aba"，最长公共前后缀是"a"，长度为1。
• 下标3的字符是'b'，子串为"abab"，最长公共前后缀是"ab"，长度为2。

所以前缀函数数组是[0, 0, 1, 2]。

这个数组的最后一个值（记为len_prefix）就是整个字符串的最长公共前后缀长度。现在有一个关键结论：如果字符串s确实是由某个子串重复多次构成的，那么s.length() % (s.length() - len_prefix) == 0成立。注意这里有个前提条件，公共前后缀长度必须大于0，且n % (n - len_prefix) == 0，否则不满足重复构成的条件。

这个公式是怎么来的？我用日常的例子解释一下。假设s = "ababab"，它的最长公共前后缀是"abab"，长度是4。那么n - len_prefix = 6 - 4 = 2，这个2就是"最小重复单元"的长度，对应子串"ab"。为什么？因为最长公共前后缀相当于把整个字符串"错位"后依然能重合的部分，重合部分的长度越靠近n，说明字符串整体结构越"周期化"。错位的长度（也就是n - len_prefix）就等于一个完整的周期长度。

再验证一下是否整除：6 % 2 == 0，说明字符串刚好由3个"ab"组成，结果返回true。再比如"aba"，n=3，前缀函数数组是[0, 0, 1]，最后一位len_prefix=1，n - len_prefix = 2，3 % 2 != 0，返回false。这和我们预期的结果一致。

写成代码就是：

class Solution: def repeatedSubstringPattern(self, s: str) -> bool: n = len(s) nxt = [0] * n for i in range(1, n): j = nxt[i - 1] while j > 0 and s[i] != s[j]: j = nxt[j - 1] if s[i] == s[j]: j += 1 nxt[i] = j p = n - nxt[-1] if p == n: return False return n % p == 0

这里有几个容易踩的坑。第一个坑：p可能等于n。这种情况发生在最长公共前后缀长度为0时，比如"abc"，此时n - 0 = n，如果直接算n % n == 0就会错误地返回true，所以要提前判断p == n的情况。第二个坑：即使p < n，也要判断是否能整除。比如"abac"，它并不是由某个子串重复构成的，但它的最长公共前后缀长度可能不为零，此时n % p就不一定等于0。

这个推导逻辑是我建议所有刷到这道题的人都动手推一遍的。推完之后，你对KMP里前缀函数"为什么有用"会有更直观的认识，而不是单纯背模板。

3.3 解法二：s + s去头去尾法

接下来是那个"一行解法"。思路是这样的：把字符串s和s拼接成s + s，然后删除新字符串的第一个字符和最后一个字符，再在这个新字符串里查找s是否仍然存在。如果存在，返回true；否则返回false。

这个思路的正确性源于一个很巧妙的观察：如果一个字符串s是由某个子串t重复多次构成的（比如"abab"由t="ab"重复两次构成），那么在s + s中，s一定会在一个非起始位置再次出现。删掉首尾字符是为了排除掉那种"s在s+s里出现的唯一位置恰好就是原始s的完整拷贝"的干扰。

再用一个反面例子帮助理解。假设s="aba"，它不是由某子串重复构成的。那么s+s="abaaba"，去掉首尾变成"baab"，我们在这个字符串中查找"aba"，查不到，所以返回false。

这个解法的代码实现可以非常简洁：

class Solution: def repeatedSubstringPattern(self, s: str) -> bool: return s in (s + s)[1:-1]

这里的核心是Python的in操作，它底层使用的是高效的字符串搜索算法。如果不依赖内置函数，也可以把s + s的查找步骤改成KMP来进行，思路是一样的。

这个解法从代码量上看非常讨喜，但它最大的价值在于证明过程。如果哪天面试时你只写这行代码而不解释为什么成立，面试官大概率会继续追问，因为这不像是"想清楚后写出来的"，更像是"背了一个trick"。我建议大家在理解KMP解法之后再来理解这个trick，两者会互相印证。

3.4 两种解法的复杂度对比

用一张表来总结一下四种实现方式的复杂度与适用场景：

在实际刷力扣时，第一种枚举法拿来做鲁棒性测试和验证还是可以的，但真正提交到LeetCode上，我通常直接写KMP解法或s+s解法。简单题的目标不是"能过"，而是"最优且能讲清原理"。

4. 做题过程中的常见错误与细节坑

4.1 KMP前缀函数计算的边界

我在写459题的KMP解法时，第一版代码里犯过一个典型错误：初始化next数组时，没有正确处理不存在公共前后缀的情况。如果字符串只有1个字符，比如"a"，那么n=1，循环for i in range(1, n)不会执行，nxt[-1]此时访问的是下标0的位置，值是0，p = 1 - 0 = 1，p == n返回false，这个用例倒是能过。

但如果字符串是"aa"，n=2，前缀函数计算得到的数组是[0, 1]，nxt[-1]=1，p=1，2 % 1 == 0，返回true。结果正确，因为"aa"确实可以由"a"重复两次构成。

真正容易出的问题是在更新j的循环条件上。很多人在计算next[i]时会写成while j > 0 and s[i] != s[j]，但忘记回退到j = nxt[j - 1]，导致死循环。这里其实就是KMP匹配失败时的经典回退动作，可以把它理解成：既然s[j]匹配不上，那就去看更短一点的公共前后缀还有没有机会，也就是j往前跳。这一步没有理解透的话，KMP整段代码都会是记模板的状态。

4.2 459题判断整除时的漏判

前面提过，必须有p == n的判断，否则"abc"这类没有重复单元的字符串会返回true。这个坑我用一句话提醒自己：n % p == 0成立不代表一定是重复子串，还必须满足p < n。在数学上，任何数都能被它自身整除，所以整除条件必须和长度条件同时成立。

4.3 1768题中最容易忽视的while写法

1768常见的错误是把while条件写成while i < len(word1) and j < len(word2)，然后把剩余字符用两个额外的循环单独处理。这种写法没有问题，但如果两个剩余循环里都用了res.append(word1[i:])（直接拼一个子串），注意这里的子串长度可能大于1，这是允许的。我之前见过有人在这里把切片写成word1[i]，导致只追加了一个字符，剩下的字符全丢了。这个错误很低级，但是在紧张状态下确实容易犯，一定要试一组长短差异明显的测试用例来验证。

4.4 做题时怎么自查

我的建议是，每做完一道题，至少跑三组测试用例：

• 题目给的官方示例。
• 边界条件：空字符串（题目通常说非空，但自己的函数要考虑到）、单字符、两个字符串等长、其中一个特别短。
• 容易判断错的反例：459题多试试"aba"、"abcab"、"aabaab"这类不是重复单元构成的字符串。

这组反例往往比正例更能验证代码的正确性，因为在正例上代码大概率能跑通，反例才能真正检验你对边界条件的处理。

5. 从两题看刷题方法论

5.1 简单题如何刷出复利

不少人刷题有个误区：觉得简单题没营养，直接跳过，只刷中等和难题。但我自己刷了一段时间后的体感是：简单题里也分好几个层次。有的简单题是纯签到题，确实只要会循环就会写；有的简单题，比如459这种，它背后可以牵扯出KMP、字符串匹配、数学证明，你愿意挖多深就能挖多深。

所以我在刷题记录里会给每道题做标签。1768的标签是"双指针、模拟、热身"，459的标签是"字符串、KMP、前缀函数、数学推导"。这两个标签让我在第三天回顾时，能够迅速想起当时练习的知识点，而不用重新读一遍题目。

5.2 一个有效的刷题流程

我自己常用的刷题流程是这样的：

• 第一步，拿到题目后先手写样例，模拟一遍过程，明确输出结果。
• 第二步，先想暴力解法，不要嫌它慢，它是一个可靠的基准答案。
• 第三步，分析暴力解法里有哪些重复计算，尝试优化。这一步往往就是双指针、哈希表、动态规划等技巧的入口。
• 第四步，保证正确性后，再看有没有思路更简洁的数学或匹配解法。
• 第五步，写完代码后跑三个方向的反例，确认没有边界遗漏。
• 第六步，把题目和核心思路记到刷题记录里，标注知识点和需要复盘的坑。

459题就很典型：暴力解法是枚举可能的子串长度，复杂度O(n^2)。优化方向具体来说有两个，一是用KMP把匹配过程的复杂度降到O(n)，二是利用s+s的数学性质直接判断。两条路都能走通，但只有走到第四步的人才能同时掌握两种思路。

5.3 为什么建议把459和1768放在一起刷

我在标题里记的是"力扣刷题459和1768"，确实是同一天做的。当时的感觉是：1768花了几分钟写完，完全没压力，让手热起来；然后做459，第一反应写了个双循环枚举，提交通过了但时间复杂度不理想，于是沉下心来推导KMP解法。这两题的节奏差异很大，恰好适合用来练习"从舒适区进入挑战区"的切换能力。

如果是刚接触力扣刷题的新手，我推荐把1768作为独立的热身题先做，再做459。如果是想巩固字符串匹配知识点的人，可以直接用459作为复习KMP的入口，然后再额外刷几道同样用到前缀函数的题目，比如力扣28题"找出字符串中第一个匹配项的下标"，效果会更好。

5.4 刷题记录里应该写什么

不少人在刷题记录里只写"今天做了XX题，AC了"，其实信息量很低。真正有价值的记录至少应该包含：

• 题号、题名、难度和涉及的核心知识点。
• 这次用的解法和复杂度。
• 踩过哪些坑，尤其是有没有提交失败的经历，失败原因是边界条件、索引越界还是逻辑错误。
• 有没有比官方题解更好的角度，或者和自己之前写的同类题目有什么联系。
• 下次复习时优先看哪些部分。

这样记录的好处是，一个月后翻出来看，不需要重新读题就能快速回忆起题目核心和解法。这也是我坚持在做的事。

最后再分享一个小技巧：如果你发现一道简单题想了很久也没有思路，尤其是像459这种你已经知道存在O(n^2)解法但觉得不够好时，不妨先把它标记起来，隔天再回头看。很多时候，灵感并不是在死磕时产生的，而是在换了一个轻松的心态后突然想通的。我在459上就是先放下了枚举法，睡了一觉之后，第二天重新推导KMP时才彻底明白了那个n % (n - next[-1])公式的含义。刷题这件事，比堆数量更重要的，是把每道题背后"凭什么这样解"想清楚。