1. 整体设计与思路拆解为什么是这四道题字符串处理算是算法题里最“实在”的一类题目因为你在日常开发里几乎天天和它打交道用户输入校验、关键词高亮、文本编辑器的撤销操作、URL解析、日志切割甚至数据库里的模糊查询底层都离不开字符串的遍历、翻转和匹配。这次要聊的四个题目——反转字符串、反转字符串2、翻转字符串里的单词、重复的子字符串恰好构成了字符串操作的一条清晰学习路径从最基础的原地修改到分段边界处理再到综合性的多步操作最后上升到模式匹配。先说一个可能很多人忽略的事实反转字符串这件事本身并不难难的是“在什么约束条件下反转”。比如“反转字符串”要求原地修改、O(1)额外空间这就排除了新建一个字符串再倒着拷贝的偷懒方案到了“反转字符串2”约束变成了“每2k个字符反转前k个字符”看似只是加了规则实际上考验的是你写循环时对区间的控制力“翻转字符串里的单词”则把问题升级成“先清理空格、再整体翻转、最后逐个单词翻转”的多阶段流程“重复的子字符串”更是直接跳到了KMP算法用next数组判断一个字符串是否存在循环节。所以这四道题不是孤立的它们之间存在明显的递进关系。我自己的感受是如果把这一组题连续刷完你对“下标区间”“循环不变量”“双指针”这三件事的理解会明显上一个台阶。尤其是对准备面试的同学来说这几道题出现的频率相当高面试官很喜欢用它们来考察你写代码时是否考虑边界条件以及你的代码是否简洁清晰。这套题适合谁一个是刚学完基础语法、准备开始刷算法的初学者可以通过它们建立对双指针和KMP的直觉另一个是刷题一段时间但总觉得字符串类题目不稳定的同学这四道题能帮你把分散的知识点串联起来。本文会把每一道题的思路、为什么这么想、完整代码、复杂度分析以及我踩过的坑都拆开讲一遍你可以直接照着写也可以只看思路部分再自己实现。2. 核心细节解析与实操要点2.1 反转字符串原地修改与双指针边界题目要求很简单输入一个字符数组原地反转。不能额外申请数组空间复杂度要求O(1)。这几乎是双指针最经典的入门场景了。思路是左右两个指针一个从头部往右走一个从尾部往左走每次交换两个位置的字符直到两个指针相遇或者交错。这里有一个新手经常纠结的点循环条件用left right还是left right答案是left right。因为在left right的时候两个指针指向同一个位置交换它和自己没有任何意义多一次无效操作而已。用left right还有一个好处——不需要单独考虑字符数组长度为奇数还是偶数因为中间那个字符在指针相遇时自然被跳过不会被错误交换。void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }复杂度是O(n)时间O(1)空间没有更优的解法了因为每个字符至少要移动一次。这里要说一个面试中的实际观察很多候选人会直接调用库函数或者用reverse(s.begin(), s.end())然后说“这样就行了”。这种答案不是错但面试官大概率会追问“如果让你自己实现你怎么做”。所以这道题真正的考察点不是你能不能反转而是你有没有理解双指针交换的本质。建议刷题时不要图省事手写交换逻辑把每一步的指针变化在纸上画出来。2.2 反转字符串2分段处理与区间计算“反转字符串2”的规则是给定一个字符串s和一个整数k从字符串开头算起每计数至2k个字符就反转这2k个字符中的前k个字符。如果剩余字符少于k个则将剩余字符全部反转如果剩余字符大于等于k个且小于2k个则反转前k个字符其余字符保持原样。初次看到这个规则很容易懵记住一个判断技巧每一段都是独立的段的长度是2k段内只处理前k个。我们不需要真的把字符串切成一段段再拼接只需要让循环的步长是2k然后对s[i, ik)这个区间做反转。string reverseStr(string s, int k) { int n s.size(); for (int i 0; i n; i 2 * k) { int left i; int right min(i k - 1, n - 1); while (left right) { swap(s[left], s[right]); left; right--; } } return s; }这里最关键的一行是int right min(i k - 1, n - 1)。它同时处理了两种边界情况当剩余字符不足k个时i k - 1会越界取n - 1正好把剩余全部反转当剩余字符在k到2k之间时右边界是i k - 1后面的字符不碰正好符合题目要求。这道题的核心考点是“步长”和“区间裁剪”。我见过不少实现是分段讨论、每种情况写一个if分支结果代码又长又容易漏。用步长循环加上min裁剪区间可以把所有情况统一成一套逻辑。写完之后建议用几个典型用例验证一下k1、k3、n4、n5、n6尤其是n恰好等于2k的整数倍的情况。2.3 翻转字符串里的单词空格清理与多次反转的配合“翻转字符串里的单词”是这四道题里综合性最强的。题目要求输入一个英文句子翻转每个单词的顺序但单词内部字符顺序不变同时要去掉多余的空格比如首尾空格、单词之间的连续空格都要清理。最经典的解法是“先整体反转再逐个单词反转”。举个具体例子帮助理解输入hello world先整体反转得到dlrow olleh你会发现整句话的顺序反了但每个单词内部的字母也反了。这时候再对每个单词内部做一次反转dlrow变回worldolleh变回hello结果变成world hello正好是目标答案。这个思路可以用生活类比来理解想象一叠卡片每张卡片上写着一个单词。先整个翻过来卡片的顺序反了再手动把每张卡片旋转180度卡片上的字就正了但卡片顺序还是反的。两次反转配合达到单词顺序翻转、单词内容不变的效果。在实现上比较推荐的做法是先写一个reverseRange(s, start, end)辅助函数只反转字符串中指定区间。然后string reverseWords(string s) { // 1. 去除多余空格 // 2. 整体反转 // 3. 逐个单词反转 }去除多余空格这一步看起来简单但特别容易出问题。如果你用C可以用双指针原地清理一个快指针遍历原字符串一个慢指针记录写入位置。跳过开头的连续空格遇到单词就写到慢指针位置单词之间只保留一个空格。注意最后要把字符串缩到实际长度。// 原地清理空格 int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow);这段代码里有个小细节if (slow ! 0) s[slow] ;是为了在单词之间插入空格。第一次遇到非空格字符时slow还是0说明是第一个单词不加空格后续每遇到一个新单词开头先补一个空格再写入单词内容。这个设计的精妙之处在于它自动处理了首尾空格和连续空格不用单独判断。清理完空格后整体反转然后遍历字符串遇到空格或走到末尾就反转当前单词区间。整个过程虽然步骤多但每一步都很清晰。如果你用的是Python可以直接split()再倒序拼接代码几行就搞定。但我建议还是手动实现一遍原地版本因为面试时手写split版本虽然简单却体现不出你对字符串操作的控制力。2.4 重复的子字符串从简单思路到KMP第四题“重复的子字符串”和前三个不太一样它不再只依赖双指针而是要判断一个字符串是否可以由某个子串重复多次构成。比如abab可以由ab重复两次构成abcabcabc可以由abc重复三次构成而aba不行。先讲一个看起来很直观的思路枚举可能的子串长度。如果字符串长度为n那么子串长度len必须能被n整除否则无法重复整数次。于是从1到n/2遍历len对每个能整除n的len截取前缀子串然后重复拼接判断是否等于原字符串。这种方式的时间复杂度是O(n²)虽然能过但不够优雅而且面试官大概率会追问“有没有更好的方法”。更好的方法是KMP算法。具体做法是求出字符串的前缀函数next数组记next[n-1]为整个字符串的最长相等前后缀长度。如果next[n-1] 0且n % (n - next[n-1]) 0那么字符串就是由某个子串重复构成的重复子串的长度为n - next[n-1]。为什么这个条件成立我一开始也被这个结论绕晕过后来用“周期”的概念才彻底理解。最长相等前后缀的意思是字符串的前next[n-1]个字符和后next[n-1]个字符完全相同。如果字符串存在循环节那么n - next[n-1]正好是一个循环节的长度总长度能被循环节长度整除说明循环节重复了整数次。反过来如果整段字符串的前后缀重合部分达到了n - 一个循环节长度那字符串一定具有周期性。举个例子验证ababnext数组是[0, 0, 1, 2]next[3]2n - next[3] 4 - 2 24 % 2 0所以存在重复子串长度为2即ab。再看abanext数组是[0, 0, 1]next[2]1n - next[2] 3 - 1 23 % 2 ! 0所以不存在重复子串。bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; } if (s[i] s[j]) { j; } next[i] j; } int len n - next[n - 1]; return next[n - 1] 0 n % len 0; }这道题的难点在于KMP本身。很多人觉得KMP很难其实只要记住next数组的本质——“当前位置之前的最长相同前缀后缀的长度”再配合“失配时回退到next[j-1]”这一句话就能把代码模板背下来。不要试图死记硬背而是拿ababaca这种经典串在纸上手动推导一遍next数组的生成过程理解之后代码自然就写出来了。3. 实操过程与核心环节实现3.1 环境准备与测试框架这几道题不依赖特殊的编译环境本地随便一个支持C17的编译器就行。我习惯在本地写一个简单的测试函数把关键用例一次性跑完确认无误后再提交到在线判题系统。这样调试效率最高还能避免反复提交浪费耐心。一个实用的测试结构如下#include iostream #include vector #include string using namespace std; void test(string name, bool result) { cout name : (result ? PASS : FAIL) endl; } int main() { // 反转字符串 vectorchar s1 {h,e,l,l,o}; reverseString(s1); test(reverseString, s1[0]o s1[4]h); // 反转字符串2 test(reverseStr, reverseStr(abcdefg, 2) bacdfeg); // 翻转字符串里的单词 test(reverseWords, reverseWords( hello world ) world hello); // 重复的子字符串 test(repeatedSubstringPattern, repeatedSubstringPattern(abcabcabcabc) true); test(repeatedSubstringPattern2, repeatedSubstringPattern(aba) false); return 0; }这种测试方式的优点是直观哪个用例挂了立刻知道。我把四道题的代码放在同一个文件里分别定义好函数然后统一跑测试。刷题阶段保持“分而治之”的测试习惯能帮你快速定位错误是出在算法逻辑还是边界情况。3.2 完整代码与逐行注释下面给出四道题的完整实现以C为例每段代码都加了注释。我特意在注释里标出了容易出错的边界位置方便直接对照。// 题目1反转字符串 void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } // 题目2反转字符串2 string reverseStr(string s, int k) { int n s.size(); for (int i 0; i n; i 2 * k) { int left i; int right min(i k - 1, n - 1); // 关键裁剪越界 while (left right) { swap(s[left], s[right]); left; right--; } } return s; } // 题目3翻转字符串里的单词 string reverseWords(string s) { // 第一步去除多余空格首尾和连续空格 int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow); // 第二步整体反转 reverse(s.begin(), s.end()); // 第三步逐个单词反转 int start 0; for (int i 0; i s.size(); i) { if (i s.size() || s[i] ) { reverse(s.begin() start, s.begin() i); start i 1; } } return s; } // 题目4重复的子字符串 bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; // 失配回退 } if (s[i] s[j]) { j; } next[i] j; } int cycleLen n - next[n - 1]; // 循环节长度 return next[n - 1] 0 n % cycleLen 0; }第三题里我用了reverse库函数来简化局部反转的代码如果你不想依赖库函数可以仿照第一题写一个reverseRange(s, left, right)辅助函数效果一样。重点是理解“整体反转局部反转”的思路而不是纠结用不用库函数。代码写完后我本地跑了一下测试输出结果如下reverseString: PASS reverseStr: PASS reverseWords: PASS repeatedSubstringPattern: PASS repeatedSubstringPattern2: PASS通过全部用例。这里想提醒一个细节“翻转字符串里的单词”的第三步循环条件是i s.size()而不是i s.size()这是为了在字符串末尾处也能触发一次单词反转。因为最后一个单词后面不一定有空格必须让循环走到s.size()这个虚拟位置才不会被漏掉。3.3 复杂度对比与面试要点四道题的时间复杂度和空间复杂度对比如下题目时间复杂度空间复杂度核心技巧反转字符串O(n)O(1)双指针反转字符串2O(n)O(1)步长循环 区间裁剪翻转字符串里的单词O(n)O(1)去空格 两次反转重复的子字符串O(n)O(n)KMP前缀函数前三个都是原地修改空间复杂度做到O(1)第四题需要额外的next数组空间复杂度O(n)。第四题其实也有另一种拼接字符串的思路把原字符串拼接成ss然后去掉首尾各一个字符如果原字符串是重复子串构成那么s一定包含在新字符串里。这个思路实现简单但面试时容易被追问原理所以我还是推荐掌握KMP解法。面试中的表达也很重要。比如第二题不要只说“我循环步长2k”要解释为什么步长是2k因为题目要求每2k个字符处理一次而且每次处理只反转前k个。还有第四题不要只说“用KMP套模板”要能解释next[n-1]和循环节长度的关系。能把“为什么”讲清楚比默写代码更能加分。4. 常见问题与排查技巧实录4.1 双指针边界问题速查字符串反转类题目最常见的错误就是边界判断出错。我整理了一套自查清单几乎可以覆盖所有双指针反转场景空字符串或长度为1的字符串直接返回不会进入交换逻辑。长度为偶数最后一个有效交换发生在left n/2 - 1、right n/2时交换后leftright循环结束。长度为奇数中间字符不会被交换因为此时left right循环条件left right为假。记住一句话右指针永远指向有效下标左指针不超过右指针。凡是出现越界先检查右指针的初始化和更新逻辑。4.2 翻转单词时的空格细节翻转字符串里的单词最大的坑在空格处理上。我统计自己在本地调试时遇到的几个典型问题第一首尾空格没有清理干净。如果直接整体反转首尾空格会跑到中间去导致后续单词反转时出现多余空串。所以必须先清理空格再反转。第二连续多个空格只保留一个。清理逻辑里if (slow ! 0) s[slow] 这个设计就是为了保证每个单词前只补一个空格但你要注意它只在单词开头触发不会在单词内部触发。第三C里清理完空格后一定要resize否则字符串尾部还会残留旧字符输出时会看到莫名其妙的垃圾字符。Python选手如果手写原地版本要格外小心字符串不可变的问题。你不能像C那样直接resize而是要先转成list处理完再转回字符串。这也是为什么Python解法直接用split()最省事但原理层面还是要懂。4.3 重复子字符串判断中的KMP误区KMP解法里最容易混淆的是next数组的含义和最终判断条件。我拆成三点来说第一点next[i]表示的是“以i结尾的子串”的最长相等前后缀长度不是整个字符串的。因此最终判断要看next[n-1]而不是遍历找最大值。第二点n - next[n-1]是循环节长度的前提是“字符串存在循环节”。如果next[n-1] 0说明没有相等前后缀n - 0 n虽然n % n 0但这样会误判“整个字符串作为自己的重复子串”这显然不对。所以判断条件必须加上next[n-1] 0。这一点是网上很多讲解容易漏掉的地方。第三点理解“为什么整除条件成立”。举个例子感受一下字符串abacabanext数组最后一个值是3n - 3 47 % 4 ! 0所以不是重复子串构成。而abcabcnext数组最后一个值是3n - 3 36 % 3 0存在长度为3的循环节abc。看不出来的时候把字符串和它的next数组画出来对比会比空想清楚很多。4.4 避坑清单与实战心得最后分享几条我自己刷这组题攒下来的经验都是文档里不会写但实际很管用的东西。不要急着调库函数。尤其是前两道反转题用std::reverse一步到位虽然爽但你失去了练习手写双指针的机会。面试时一旦库函数被禁用你会突然发现自己连最基础的反转都写不利索。建议前两道题强制自己手写交换第三题再放开用库函数。每组边界用例都要跑一遍。我的习惯是每道题至少准备五个用例空字符串、单字符、正好2k长度、2k-1长度、2k1长度。这些用例跑通了边界问题基本就不会漏。特别是第二题n和k的各种大小关系组合起来情况不少但用min裁剪后一套逻辑就能全覆盖。调试时打印中间状态。第三题特别建议在“清理空格后”、“整体反转后”、“每个单词反转后”分别打印一次当前字符串。这样一眼就能看出是哪一步把顺序搞错了。别嫌麻烦字符串题出bug后肉眼debug效率最高。学习和整理时把四道题放在一起。它们不是独立的个体而是一条完整的进阶链路。先练双指针基础再练分段边界再练多步骤综合操作最后练模式匹配。我个人的做法是把这四道题的思路浓缩到一张A4纸上左边是四段核心代码骨架右边是边界条件和易错点。面试前只看这张纸比重新翻题解高效很多。后续扩展的方向。这套思路还可以延伸到不少相关题目比如“反转链表”里的区间反转、字符串循环右移、判断旋转字符串ss包含s等核心思路都离不开“区间反转”和“周期判断”。刷完这组题后把这些变体再扫一遍字符串类题目的手感会稳很多。
1. 整体设计与思路拆解为什么是这四道题字符串处理算是算法题里最“实在”的一类题目因为你在日常开发里几乎天天和它打交道用户输入校验、关键词高亮、文本编辑器的撤销操作、URL解析、日志切割甚至数据库里的模糊查询底层都离不开字符串的遍历、翻转和匹配。这次要聊的四个题目——反转字符串、反转字符串2、翻转字符串里的单词、重复的子字符串恰好构成了字符串操作的一条清晰学习路径从最基础的原地修改到分段边界处理再到综合性的多步操作最后上升到模式匹配。先说一个可能很多人忽略的事实反转字符串这件事本身并不难难的是“在什么约束条件下反转”。比如“反转字符串”要求原地修改、O(1)额外空间这就排除了新建一个字符串再倒着拷贝的偷懒方案到了“反转字符串2”约束变成了“每2k个字符反转前k个字符”看似只是加了规则实际上考验的是你写循环时对区间的控制力“翻转字符串里的单词”则把问题升级成“先清理空格、再整体翻转、最后逐个单词翻转”的多阶段流程“重复的子字符串”更是直接跳到了KMP算法用next数组判断一个字符串是否存在循环节。所以这四道题不是孤立的它们之间存在明显的递进关系。我自己的感受是如果把这一组题连续刷完你对“下标区间”“循环不变量”“双指针”这三件事的理解会明显上一个台阶。尤其是对准备面试的同学来说这几道题出现的频率相当高面试官很喜欢用它们来考察你写代码时是否考虑边界条件以及你的代码是否简洁清晰。这套题适合谁一个是刚学完基础语法、准备开始刷算法的初学者可以通过它们建立对双指针和KMP的直觉另一个是刷题一段时间但总觉得字符串类题目不稳定的同学这四道题能帮你把分散的知识点串联起来。本文会把每一道题的思路、为什么这么想、完整代码、复杂度分析以及我踩过的坑都拆开讲一遍你可以直接照着写也可以只看思路部分再自己实现。2. 核心细节解析与实操要点2.1 反转字符串原地修改与双指针边界题目要求很简单输入一个字符数组原地反转。不能额外申请数组空间复杂度要求O(1)。这几乎是双指针最经典的入门场景了。思路是左右两个指针一个从头部往右走一个从尾部往左走每次交换两个位置的字符直到两个指针相遇或者交错。这里有一个新手经常纠结的点循环条件用left right还是left right答案是left right。因为在left right的时候两个指针指向同一个位置交换它和自己没有任何意义多一次无效操作而已。用left right还有一个好处——不需要单独考虑字符数组长度为奇数还是偶数因为中间那个字符在指针相遇时自然被跳过不会被错误交换。void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }复杂度是O(n)时间O(1)空间没有更优的解法了因为每个字符至少要移动一次。这里要说一个面试中的实际观察很多候选人会直接调用库函数或者用reverse(s.begin(), s.end())然后说“这样就行了”。这种答案不是错但面试官大概率会追问“如果让你自己实现你怎么做”。所以这道题真正的考察点不是你能不能反转而是你有没有理解双指针交换的本质。建议刷题时不要图省事手写交换逻辑把每一步的指针变化在纸上画出来。2.2 反转字符串2分段处理与区间计算“反转字符串2”的规则是给定一个字符串s和一个整数k从字符串开头算起每计数至2k个字符就反转这2k个字符中的前k个字符。如果剩余字符少于k个则将剩余字符全部反转如果剩余字符大于等于k个且小于2k个则反转前k个字符其余字符保持原样。初次看到这个规则很容易懵记住一个判断技巧每一段都是独立的段的长度是2k段内只处理前k个。我们不需要真的把字符串切成一段段再拼接只需要让循环的步长是2k然后对s[i, ik)这个区间做反转。string reverseStr(string s, int k) { int n s.size(); for (int i 0; i n; i 2 * k) { int left i; int right min(i k - 1, n - 1); while (left right) { swap(s[left], s[right]); left; right--; } } return s; }这里最关键的一行是int right min(i k - 1, n - 1)。它同时处理了两种边界情况当剩余字符不足k个时i k - 1会越界取n - 1正好把剩余全部反转当剩余字符在k到2k之间时右边界是i k - 1后面的字符不碰正好符合题目要求。这道题的核心考点是“步长”和“区间裁剪”。我见过不少实现是分段讨论、每种情况写一个if分支结果代码又长又容易漏。用步长循环加上min裁剪区间可以把所有情况统一成一套逻辑。写完之后建议用几个典型用例验证一下k1、k3、n4、n5、n6尤其是n恰好等于2k的整数倍的情况。2.3 翻转字符串里的单词空格清理与多次反转的配合“翻转字符串里的单词”是这四道题里综合性最强的。题目要求输入一个英文句子翻转每个单词的顺序但单词内部字符顺序不变同时要去掉多余的空格比如首尾空格、单词之间的连续空格都要清理。最经典的解法是“先整体反转再逐个单词反转”。举个具体例子帮助理解输入hello world先整体反转得到dlrow olleh你会发现整句话的顺序反了但每个单词内部的字母也反了。这时候再对每个单词内部做一次反转dlrow变回worldolleh变回hello结果变成world hello正好是目标答案。这个思路可以用生活类比来理解想象一叠卡片每张卡片上写着一个单词。先整个翻过来卡片的顺序反了再手动把每张卡片旋转180度卡片上的字就正了但卡片顺序还是反的。两次反转配合达到单词顺序翻转、单词内容不变的效果。在实现上比较推荐的做法是先写一个reverseRange(s, start, end)辅助函数只反转字符串中指定区间。然后string reverseWords(string s) { // 1. 去除多余空格 // 2. 整体反转 // 3. 逐个单词反转 }去除多余空格这一步看起来简单但特别容易出问题。如果你用C可以用双指针原地清理一个快指针遍历原字符串一个慢指针记录写入位置。跳过开头的连续空格遇到单词就写到慢指针位置单词之间只保留一个空格。注意最后要把字符串缩到实际长度。// 原地清理空格 int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow);这段代码里有个小细节if (slow ! 0) s[slow] ;是为了在单词之间插入空格。第一次遇到非空格字符时slow还是0说明是第一个单词不加空格后续每遇到一个新单词开头先补一个空格再写入单词内容。这个设计的精妙之处在于它自动处理了首尾空格和连续空格不用单独判断。清理完空格后整体反转然后遍历字符串遇到空格或走到末尾就反转当前单词区间。整个过程虽然步骤多但每一步都很清晰。如果你用的是Python可以直接split()再倒序拼接代码几行就搞定。但我建议还是手动实现一遍原地版本因为面试时手写split版本虽然简单却体现不出你对字符串操作的控制力。2.4 重复的子字符串从简单思路到KMP第四题“重复的子字符串”和前三个不太一样它不再只依赖双指针而是要判断一个字符串是否可以由某个子串重复多次构成。比如abab可以由ab重复两次构成abcabcabc可以由abc重复三次构成而aba不行。先讲一个看起来很直观的思路枚举可能的子串长度。如果字符串长度为n那么子串长度len必须能被n整除否则无法重复整数次。于是从1到n/2遍历len对每个能整除n的len截取前缀子串然后重复拼接判断是否等于原字符串。这种方式的时间复杂度是O(n²)虽然能过但不够优雅而且面试官大概率会追问“有没有更好的方法”。更好的方法是KMP算法。具体做法是求出字符串的前缀函数next数组记next[n-1]为整个字符串的最长相等前后缀长度。如果next[n-1] 0且n % (n - next[n-1]) 0那么字符串就是由某个子串重复构成的重复子串的长度为n - next[n-1]。为什么这个条件成立我一开始也被这个结论绕晕过后来用“周期”的概念才彻底理解。最长相等前后缀的意思是字符串的前next[n-1]个字符和后next[n-1]个字符完全相同。如果字符串存在循环节那么n - next[n-1]正好是一个循环节的长度总长度能被循环节长度整除说明循环节重复了整数次。反过来如果整段字符串的前后缀重合部分达到了n - 一个循环节长度那字符串一定具有周期性。举个例子验证ababnext数组是[0, 0, 1, 2]next[3]2n - next[3] 4 - 2 24 % 2 0所以存在重复子串长度为2即ab。再看abanext数组是[0, 0, 1]next[2]1n - next[2] 3 - 1 23 % 2 ! 0所以不存在重复子串。bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; } if (s[i] s[j]) { j; } next[i] j; } int len n - next[n - 1]; return next[n - 1] 0 n % len 0; }这道题的难点在于KMP本身。很多人觉得KMP很难其实只要记住next数组的本质——“当前位置之前的最长相同前缀后缀的长度”再配合“失配时回退到next[j-1]”这一句话就能把代码模板背下来。不要试图死记硬背而是拿ababaca这种经典串在纸上手动推导一遍next数组的生成过程理解之后代码自然就写出来了。3. 实操过程与核心环节实现3.1 环境准备与测试框架这几道题不依赖特殊的编译环境本地随便一个支持C17的编译器就行。我习惯在本地写一个简单的测试函数把关键用例一次性跑完确认无误后再提交到在线判题系统。这样调试效率最高还能避免反复提交浪费耐心。一个实用的测试结构如下#include iostream #include vector #include string using namespace std; void test(string name, bool result) { cout name : (result ? PASS : FAIL) endl; } int main() { // 反转字符串 vectorchar s1 {h,e,l,l,o}; reverseString(s1); test(reverseString, s1[0]o s1[4]h); // 反转字符串2 test(reverseStr, reverseStr(abcdefg, 2) bacdfeg); // 翻转字符串里的单词 test(reverseWords, reverseWords( hello world ) world hello); // 重复的子字符串 test(repeatedSubstringPattern, repeatedSubstringPattern(abcabcabcabc) true); test(repeatedSubstringPattern2, repeatedSubstringPattern(aba) false); return 0; }这种测试方式的优点是直观哪个用例挂了立刻知道。我把四道题的代码放在同一个文件里分别定义好函数然后统一跑测试。刷题阶段保持“分而治之”的测试习惯能帮你快速定位错误是出在算法逻辑还是边界情况。3.2 完整代码与逐行注释下面给出四道题的完整实现以C为例每段代码都加了注释。我特意在注释里标出了容易出错的边界位置方便直接对照。// 题目1反转字符串 void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } // 题目2反转字符串2 string reverseStr(string s, int k) { int n s.size(); for (int i 0; i n; i 2 * k) { int left i; int right min(i k - 1, n - 1); // 关键裁剪越界 while (left right) { swap(s[left], s[right]); left; right--; } } return s; } // 题目3翻转字符串里的单词 string reverseWords(string s) { // 第一步去除多余空格首尾和连续空格 int slow 0; for (int fast 0; fast s.size(); fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast s.size() s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow); // 第二步整体反转 reverse(s.begin(), s.end()); // 第三步逐个单词反转 int start 0; for (int i 0; i s.size(); i) { if (i s.size() || s[i] ) { reverse(s.begin() start, s.begin() i); start i 1; } } return s; } // 题目4重复的子字符串 bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; // 失配回退 } if (s[i] s[j]) { j; } next[i] j; } int cycleLen n - next[n - 1]; // 循环节长度 return next[n - 1] 0 n % cycleLen 0; }第三题里我用了reverse库函数来简化局部反转的代码如果你不想依赖库函数可以仿照第一题写一个reverseRange(s, left, right)辅助函数效果一样。重点是理解“整体反转局部反转”的思路而不是纠结用不用库函数。代码写完后我本地跑了一下测试输出结果如下reverseString: PASS reverseStr: PASS reverseWords: PASS repeatedSubstringPattern: PASS repeatedSubstringPattern2: PASS通过全部用例。这里想提醒一个细节“翻转字符串里的单词”的第三步循环条件是i s.size()而不是i s.size()这是为了在字符串末尾处也能触发一次单词反转。因为最后一个单词后面不一定有空格必须让循环走到s.size()这个虚拟位置才不会被漏掉。3.3 复杂度对比与面试要点四道题的时间复杂度和空间复杂度对比如下题目时间复杂度空间复杂度核心技巧反转字符串O(n)O(1)双指针反转字符串2O(n)O(1)步长循环 区间裁剪翻转字符串里的单词O(n)O(1)去空格 两次反转重复的子字符串O(n)O(n)KMP前缀函数前三个都是原地修改空间复杂度做到O(1)第四题需要额外的next数组空间复杂度O(n)。第四题其实也有另一种拼接字符串的思路把原字符串拼接成ss然后去掉首尾各一个字符如果原字符串是重复子串构成那么s一定包含在新字符串里。这个思路实现简单但面试时容易被追问原理所以我还是推荐掌握KMP解法。面试中的表达也很重要。比如第二题不要只说“我循环步长2k”要解释为什么步长是2k因为题目要求每2k个字符处理一次而且每次处理只反转前k个。还有第四题不要只说“用KMP套模板”要能解释next[n-1]和循环节长度的关系。能把“为什么”讲清楚比默写代码更能加分。4. 常见问题与排查技巧实录4.1 双指针边界问题速查字符串反转类题目最常见的错误就是边界判断出错。我整理了一套自查清单几乎可以覆盖所有双指针反转场景空字符串或长度为1的字符串直接返回不会进入交换逻辑。长度为偶数最后一个有效交换发生在left n/2 - 1、right n/2时交换后leftright循环结束。长度为奇数中间字符不会被交换因为此时left right循环条件left right为假。记住一句话右指针永远指向有效下标左指针不超过右指针。凡是出现越界先检查右指针的初始化和更新逻辑。4.2 翻转单词时的空格细节翻转字符串里的单词最大的坑在空格处理上。我统计自己在本地调试时遇到的几个典型问题第一首尾空格没有清理干净。如果直接整体反转首尾空格会跑到中间去导致后续单词反转时出现多余空串。所以必须先清理空格再反转。第二连续多个空格只保留一个。清理逻辑里if (slow ! 0) s[slow] 这个设计就是为了保证每个单词前只补一个空格但你要注意它只在单词开头触发不会在单词内部触发。第三C里清理完空格后一定要resize否则字符串尾部还会残留旧字符输出时会看到莫名其妙的垃圾字符。Python选手如果手写原地版本要格外小心字符串不可变的问题。你不能像C那样直接resize而是要先转成list处理完再转回字符串。这也是为什么Python解法直接用split()最省事但原理层面还是要懂。4.3 重复子字符串判断中的KMP误区KMP解法里最容易混淆的是next数组的含义和最终判断条件。我拆成三点来说第一点next[i]表示的是“以i结尾的子串”的最长相等前后缀长度不是整个字符串的。因此最终判断要看next[n-1]而不是遍历找最大值。第二点n - next[n-1]是循环节长度的前提是“字符串存在循环节”。如果next[n-1] 0说明没有相等前后缀n - 0 n虽然n % n 0但这样会误判“整个字符串作为自己的重复子串”这显然不对。所以判断条件必须加上next[n-1] 0。这一点是网上很多讲解容易漏掉的地方。第三点理解“为什么整除条件成立”。举个例子感受一下字符串abacabanext数组最后一个值是3n - 3 47 % 4 ! 0所以不是重复子串构成。而abcabcnext数组最后一个值是3n - 3 36 % 3 0存在长度为3的循环节abc。看不出来的时候把字符串和它的next数组画出来对比会比空想清楚很多。4.4 避坑清单与实战心得最后分享几条我自己刷这组题攒下来的经验都是文档里不会写但实际很管用的东西。不要急着调库函数。尤其是前两道反转题用std::reverse一步到位虽然爽但你失去了练习手写双指针的机会。面试时一旦库函数被禁用你会突然发现自己连最基础的反转都写不利索。建议前两道题强制自己手写交换第三题再放开用库函数。每组边界用例都要跑一遍。我的习惯是每道题至少准备五个用例空字符串、单字符、正好2k长度、2k-1长度、2k1长度。这些用例跑通了边界问题基本就不会漏。特别是第二题n和k的各种大小关系组合起来情况不少但用min裁剪后一套逻辑就能全覆盖。调试时打印中间状态。第三题特别建议在“清理空格后”、“整体反转后”、“每个单词反转后”分别打印一次当前字符串。这样一眼就能看出是哪一步把顺序搞错了。别嫌麻烦字符串题出bug后肉眼debug效率最高。学习和整理时把四道题放在一起。它们不是独立的个体而是一条完整的进阶链路。先练双指针基础再练分段边界再练多步骤综合操作最后练模式匹配。我个人的做法是把这四道题的思路浓缩到一张A4纸上左边是四段核心代码骨架右边是边界条件和易错点。面试前只看这张纸比重新翻题解高效很多。后续扩展的方向。这套思路还可以延伸到不少相关题目比如“反转链表”里的区间反转、字符串循环右移、判断旋转字符串ss包含s等核心思路都离不开“区间反转”和“周期判断”。刷完这组题后把这些变体再扫一遍字符串类题目的手感会稳很多。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
