今天刷题记录里记两道459和1768。1768是“交替合并字符串”属于力扣简单题里那种“看一眼就知道该怎么做”的题459是“重复的子字符串”标签也写着简单但牵扯到字符串周期性和KMP实际难度比很多中等题都要高。刚起步刷力扣的朋友可以把这两题当成一组搭配来练先拿1768练手找回双指针的节奏再用459来感受一下字符串题怎么从暴力解进化到最优解。我在写这篇复盘的时候并不是想把标准答案再抄一遍而是把这两道题背后的思考过程、容易踩的坑、以及它们能延伸出去的算法知识讲清楚。如果你是那种刷题只求AC、AC完就忘的人我强烈建议你跟着我的思路重新走一遍这几十分钟的复盘价值比瞎刷十道题都大。1. 选题背后的逻辑为什么偏偏是459和17681.1 两道题在题库里的定位1768题很典型它是力扣给“双指针”这个算法安排的一个入门场景。字符串本身是线性结构交替合并本质上就是同时从两个线性结构里取元素这种操作在链表合并、数组合并里非常常见。459题就有点意思了。它的题目描述非常短给定一个非空字符串s判断它能不能由它的一个子串重复多次构成。听起来好像很基础但真下手写的时候你会发现简单解法太慢快解法需要KMP而KMP又是很多人第一次接触“前缀函数”时的劝退点。所以这道题的标签虽然是简单但在力扣社区里的讨论热度一直不低。把这两题放在同一天刷其实是一种节奏安排先用1768建立信心再用459挑战一下思维深度。刷完之后你会发现两题都和字符串有关但考察的东西完全不同一个是操作维度一个是数学维度。1.2 刷题前准备不需要太重的仪式感我刷力扣的习惯是直接打开浏览器进题库用网页版编辑器写代码不额外配置IDE。力扣的在线编辑器自带测试用例和提交功能足够用了。如果你偏好本地调试装好Python环境就行这两道题用Python写代码非常舒服。另外我强烈建议你准备一个文档不是错题本而是“思维模板”。每刷完一题花两分钟写一句这题的核心思路是什么、用了什么算法、我卡在哪里。今天这两题我会在文末给出我自己的记录方式这个习惯坚持一个月你的刷题效率会有质的提升。2. 1768交替合并字符串简单题里的边界意识2.1 先读懂交替规则题目要求把word1和word2交替合并从word1的第一个字符开始轮流取一个字符拼成新的字符串。如果其中一个字符串先取完了剩下的另一个字符串的字符直接按顺序接到末尾。举个例子word1 abcword2 pqr结果是apbqcr但word1 abword2 pqrs时结果是apbqrs因为word2还剩rs没取后续全是它的字符。这个逻辑用两个下标指针分别指向两个字符串每次循环先取word1的字符再取word2的字符哪个还没越界就取哪个这是最直观的解法。核心点判断条件一定是“指针小于字符串长度”不是“等于”否则最后一个字符会被漏掉。2.2 双指针代码实现def mergeAlternately(word1: str, word2: str) - str: i, j 0, 0 res [] len1, len2 len(word1), len(word2) while i len1 or j len2: if i len1: res.append(word1[i]) i 1 if j len2: res.append(word2[j]) j 1 return .join(res)几个细节我说明一下。res用列表而不是字符串直接拼接是因为Python字符串是不可变对象每次都会生成新字符串在循环里会带来不必要的内存分配改成列表收集、最后join是工程上更合适的写法。循环结束后没有处理剩余字符因为循环体里的两个if已经覆盖了“一个指针越界、另一个继续走”的情况。如果有一个字符串是空的循环就退化成把另一个字符串的所有字符依次加进去结果和原字符串完全一致这是对的。2.3 简单题里最容易忽略的细节这题提交一次就过的概率很大但如果你去翻评论区会发现几个经典错误。第一个错误只用一个指针写一个for循环用i % 2来判断取哪个字符串的字符。这种写法在有剩余字符的情况下会乱套因为当word2很短时你还得记录word2的读取位置本质上还是双指针绕了一圈反而更麻烦。第二个错误习惯性把while条件写成while i len1 and j len2结果循环提前退出剩余字符没有处理。这种边界问题在面试时特别容易暴露不要觉得题目简单就不care代码习惯都是在这种细节里养成的。第三个错误返回值类型写错返回res列表而不是字符串。力扣判定结果时会严格比对类型[a,p]和ap是两个完全不同的东西。我的体会是1768题考察的重点不是“会不会双指针”而是“边界处理得干不干净”。双指针算法看似只有两行核心逻辑真正到了复杂场景90%的bug都出在指针越界上。所以刷完这道题建议顺手再做一遍“合并两个有序数组”你会发现边界问题的思路完全一致。3. 459重复的子字符串从暴力到KMP的进阶之路3.1 把题目翻译成数学语言题干很简短判断字符串s是否由某个子串重复多次构成。翻译一下就是是否存在一个长度L1 L n//2且L能整除n使得s[i] s[i - L]对所有i L成立。这个翻译非常关键。它告诉我们这类问题的本质是判断字符串是否具有“周期性”理解这一点之后解法就有方向了。你可以枚举可能的周期长度L也可以先算出字符串的“近似周期”再做判断。如果n是质数那除了L1和Ln之外没有其他约数答案几乎总是False除非整个字符串全部由同一个字符组成。这个数学特征可以用来快速排除一部分用例也可以用来理解为什么有些测试样例的答案那么“反直觉”。3.2 枚举法最好理解的暴力解法第一种解法是枚举子串长度。一个子串如果重复多次能组成原字符串它的长度L必须满足n % L 0而且只需要枚举到n//2即可因为大于n/2的长度不可能存在两个及以上的重复单元。def repeatedSubstringPattern(s: str) - bool: n len(s) for L in range(1, n // 2 1): if n % L ! 0: continue ok True for i in range(L, n): if s[i] ! s[i - L]: ok False break if ok: return True return False这个解法的正确性很好理解如果周期为L那么每个字符s[i]都应该等于向前数L位的那个字符s[i-L]只要有一个字符不满足这个L就不成立。时间复杂度是O(n * d(n))其中d(n)是n的约数个数。实际运行中由于每次检查都可能提前退出跑起来并不慢力扣数据下几毫秒就能完成。这种解法的优点是不依赖高级算法推导过程直白面试时如果你能先说出这个思路再逐步优化到KMP会显得思考路径特别完整。3.3 KMP解法最长相等前后缀是直接答案枚举法虽然能AC但最优解是KMP。KMP本来是用来做模式串匹配的但它的核心产物——next数组其实记录了字符串自身的前后缀信息正好可以用来判断周期性。先回顾next数组的定义next[i]表示“以i结尾的子串”的“最长相等真前后缀长度”。所谓真前后缀就是前缀和后缀不能等于整个子串本身。比如abab前缀有a,ab,aba后缀有b,ab,bab相等的最长的是ab长度是2。构建next数组的代码很多人背下来了但没理解里面的回退逻辑def build_next(s: str) - list: n len(s) nxt [0] * n j 0 for i in range(1, n): while j 0 and s[i] ! s[j]: j nxt[j - 1] if s[i] s[j]: j 1 nxt[i] j return nxt初学KMP最容易懵的地方是那个回退不匹配时j为什么要跳到nxt[j-1]而不是直接减1因为nxt[j-1]保存的是“到j-1位置为止的最长相等前后缀长度”这意味着前缀串里已经有一部分能和后缀对上直接从那里继续比较能跳过重复匹配。手动推一遍sababi0nxt[0]0i1字符bj0比较s[1]和s[0]不等nxt[1]0i2字符aj0比较s[2]和s[0]相等j变为1nxt[2]1i3字符bj1比较s[3]和s[1]相等j变为2nxt[3]2得到nxt [0,0,1,2]。拿到nxt之后怎么判断重复子串有一个关键结论如果存在某个周期长度p使得s[i] s[i-p]对所有i p成立那么字符串最长相等前后缀长度就是n-p。反过来如果最长相等前后缀长度next[n-1] 0且n % (n - next[n-1]) 0则s一定可以由周期为(n - next[n-1])的子串重复构成。这个结论的原理是最长相等前后缀把字符串拆成了三部分前next[n-1]个字符和后next[n-1]个字符相等中间剩下的就是“没有被前后缀覆盖”的那一段。如果n能被这段长度整除说明整串是由这段长度重复若干次拼出来的。写个完整代码def repeatedSubstringPattern(s: str) - bool: n len(s) nxt [0] * n j 0 for i in range(1, n): 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[n - 1] return nxt[n - 1] 0 and n % p 0这段代码最关键的判断就两行。但你要注意如果nxt[n-1]等于0说明整个字符串没有任何相等的前后缀那p就等于nn % p 0虽然成立但周期的意思是至少重复两次所以必须要有nxt[n-1] 0这个前置条件。3.4 移动匹配法里藏着一个大坑如果说KMP是502跳的进阶那下面这个“移动匹配法”就是管理视野里的另一个极端代码只要一行思路无比简单但逻辑并不严谨。网上很多解题贴会写def repeatedSubstringPattern(s: str) - bool: return s in (s s)[1:-1]意思是把s拼成两份去掉首尾字符如果还能在中间找到s说明s由重复子串构成。但这个方法有反例。试一下saabssaabaab去掉首尾变成abaab这个字符串里确实包含子串aab从下标2开始但aab并不能由某个子串重复拼接而成长度3的因数只有1和3显然不满足。也就是说这个一行代码的解法在部分用例上会返回错误答案。再试一个sabcabss去掉首尾是bcabcabca里面也能找到abcab下标3开始但abcab同样不是重复子串构成的字符串。那为什么这个解法在很多博客里被当成标准答案因为力扣的测试数据没有精确覆盖这种反例所以提交也能AC。但我建议你刷题时不要只满足于AC理解解法为什么成立或者为什么不成立才是提升的关键。如果你真的想在移动匹配的基础上修正至少还要增加一个“周期长度能整除n”的判断但那样写起来其实和枚举法差不多意义不大。3.5 三种解法的对比解法时间复杂度空间复杂度正确性风险适用场景枚举周期O(n * 约数个数)O(1)无数学推导严谨面试先手写适合快速出解KMPO(n)O(n)无正确性严谨最优解工程场景常用移动匹配O(n)O(n)存在反例不严谨只建议用来活跃思路别用于正式解题我的建议是日常刷题优先掌握枚举法和KMP。枚举法帮你建立周期性的直觉KMP则是一劳永逸的通用工具。移动匹配法可以当作闲聊时的趣味题但如果你在一个严肃场景比如面试里写出来面试官追问一句“为什么这个条件成立”很容易露馅。4. 刷题复盘两道题背后的算法思维与扩展4.1 双指针不只是“两个下标”1768里的双指针是最简单的一类两个指针同方向移动。但双指针在力扣里还有好几个常见模式相向双指针比如判断回文串、快慢双指针比如链表中找环、滑动窗口本质上也是双指针。你可以在“力扣热题100”里找到大量双指针题目从“两数之和 II”到“三数之和”再到“盛最多水的容器”它们的底层逻辑往简单说都是“用两个指针维护搜索空间”。在1768里双指针的作用是同时跟踪两个序列的读取位置。以后你写合并数组的代码核心思路一模一样先两个指针从头扫描谁小谁先进结果数组最后把剩余部分一次性拼接到末尾。4.2 字符串周期性的应用远不止这一题459的周期性判断在更多场景里是KMP算法的一个延伸。KMP最常见的用途是文本匹配比如在一些编辑器里查找关键字或者在大文本里匹配敏感词。但理解了前缀函数你还能解决像“最小循环节”这类问题这在做文本压缩、DNA序列分析时都有应用背景。如果你把459和力扣第28题“找出字符串中第一个匹配项的下标”放在一起练会很有收获。28题是典型的主串中找子串直接用KMP解459则是用KMP的next数组来判断字符串自身的周期性。一前一后你就能把KMP的Next数组从“背模板”升级成“真正理解”。4.3 从这两道题延伸出去的变式题刷题不能只满足于AC当前题目我习惯把一道题的变式也顺手想一遍。比如1768可以延伸出“把三个字符串交替合并”的问题那就要考虑用队列存储多个字符串的待读取状态459可以延伸出“输出s的最小重复子串是什么”的问题那就是在原判断逻辑成立时返回s[:p]即可。再延伸一点如果题目变成“判断s能不能由任意子串拼接而成不要求子串相同”那就是动态规划问题如果变成“判断两个字符串是不是互为循环移位”那可以直接用AA是否包含B来判断但这里必须注意包含匹配用的是KMP而不是if in因为Python的in在极端情况下也有复杂度隐患。这些延伸思考是刷一道题顶三道题的关键。4.4 我的真实刷题心得最后说点实际的。我在刷题初期最大的毛病是死磕一道题想了四十分钟还想不出来还不肯看题解结果一晚上就刷了一题。后来调整策略十五分钟想不出看题解理解后自己重新写一遍并且隔天再写一遍效果比死磕好太多。459这道题我第一次接触时也看不懂next数组的回退过程。后来找了个笨办法把next数组打印出来一行一行对照字符串观察。比如saabaaf打印next就是[0,1,0,1,2,0]你盯着这个数组看十分钟就能发现规律——它记录的其实是“当前位置与最开头位置的匹配进度”。一旦有了这个画面感KMP就不再是背模板了。复盘时我会在文档里写这么一句话1768交替合并字符串双指针基础注意两个指针独立移动循环条件用or短路边界越界判断靠if。459重复子串判断本质是字符串周期性最优解KMP的next数组判断n % (n - next[-1]) 0且next[-1] 0。这个文档积累起来之后你会发现刷题不是题号的堆积而是一个知识网络。今天这两题分别挂在“指针类”和“字符串模式匹配类”两个分类下以后遇到同类问题直接看这个模板思维路径会清晰很多。我个人还有个习惯每刷一组题挑一题用纸笔把关键算法手推一遍。459就是很好的手推对象。你把abab的next数组推导过程写在纸上再把aabaaf的next回退过程推一遍KMP的疑惑大概率能消除一大半。这种东西光看永远觉得简单自己动手推一遍才算真的会。