1. 两道题的整体定位与刷题思路先说结论今天这组合我挺满意。459和1768一个考的是字符串交替合并的模拟能力另一个考的是对字符串匹配底层原理的理解。难度上1768属于不折不扣的力扣简单题459虽然也被标成简单题但如果不熟悉KMP这类的字符串匹配算法第一次接触时很容易卡住。两题一前一后刷正好可以从会做过渡到知道为什么能这么做。我平时刷题有个习惯同一批题里尽量让题型有点差异化。热身题负责保持手感核心题负责深挖某个知识点。1768就是这个热身题五六分钟写完主要用来进入状态459则是今天的重点值得认真推导一遍把字符串匹配里的前缀函数彻底弄明白。有个细节需要先提一下459题在LeetCode上属于字符串分类经典解法有两种一种是用KMP求最长公共前后缀另一种是构造s s再去头去尾后用查找函数判断子串是否存在。后一种写法非常短几行代码就结束了但如果不知道它背后的数学推导面试时一旦被追问就很容易露馅。所以这篇记录里我会把两种解法都展开讲尤其是那个几行代码版本的证明逻辑一定要吃透。再聊聊刷题节奏。很多新手喜欢按题号从1开始一路往下刷我不太推荐这种方式。力扣热题100和力扣刷题指南这类整理好的题目列表其实更适合用来安排每日计划因为它们是按知识点和目标梯度筛选过的。459和1768这两题都属于在字符串题目中具有样板价值的题一个练模拟、一个练原理值得专门写进记录。2. 1768交替合并字符串的快速实现2.1 题目描述与直观思路题目要求很好懂给你两个字符串word1和word2把两个字符串按索引从小到大的顺序依次交替取字符合并成一个新字符串。比如word1 abcword2 pqr合并结果就是apbqcr。如果一个字符串比另一个长那么长的那个字符串剩余的部分直接接到结果末尾。举例而言word1 abword2 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(mn)空间复杂度O(mn)结果字符串本身占用的空间。如果把结果字符串的空间忽略不计额外只用了两个指针级别的辅助空间那可以认为空间复杂度是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重复两次组成结果是trueaba就不能由某个子串重复构成结果是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。再比如aban3前缀函数数组是[0, 0, 1]最后一位len_prefix1n - len_prefix 23 % 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由tab重复两次构成那么在s s中s一定会在一个非起始位置再次出现。删掉首尾字符是为了排除掉那种s在ss里出现的唯一位置恰好就是原始s的完整拷贝的干扰。再用一个反面例子帮助理解。假设saba它不是由某子串重复构成的。那么ssabaaba去掉首尾变成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 两种解法的复杂度对比用一张表来总结一下四种实现方式的复杂度与适用场景解法时间复杂度空间复杂度适用场景枚举子串长度逐个验证O(n^2)O(1)理解题意、小规模数据KMP前缀函数法O(n)O(n)标准最优解也是面试首选ss去头尾后调用inO(n)O(n)代码最简洁适合日常快速解题ss去头尾后手写KMPO(n)O(n)想深入理解匹配过程时在实际刷力扣时第一种枚举法拿来做鲁棒性测试和验证还是可以的但真正提交到LeetCode上我通常直接写KMP解法或ss解法。简单题的目标不是能过而是最优且能讲清原理。4. 做题过程中的常见错误与细节坑4.1 KMP前缀函数计算的边界我在写459题的KMP解法时第一版代码里犯过一个典型错误初始化next数组时没有正确处理不存在公共前后缀的情况。如果字符串只有1个字符比如a那么n1循环for i in range(1, n)不会执行nxt[-1]此时访问的是下标0的位置值是0p 1 - 0 1p n返回false这个用例倒是能过。但如果字符串是aan2前缀函数计算得到的数组是[0, 1]nxt[-1]1p12 % 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)二是利用ss的数学性质直接判断。两条路都能走通但只有走到第四步的人才能同时掌握两种思路。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])公式的含义。刷题这件事比堆数量更重要的是把每道题背后凭什么这样解想清楚。