1. 字符串part2的题目阵容与复习定位能把《代码随想录》刷到day09的人多半已经熬过了数组、链表、哈希表这几道坎进入字符串专题的第二阶段。说实话字符串part1大多是小打小闹——反转字符串、替换空格、翻转单词都是在原地操作或者简单遍历的层面打转。但到了part2题目风格突然就变了不再只是摆弄单个字符串而是开始考验你怎么把一个字符串拆开、重组、匹配背后牵扯到的双指针思维、KMP算法都会在后面的二叉树、动态规划里反复出现。day09这个节点很有意思。往前面看part1刚讲完反转字符串344题和替换数字卡码网54题用的是最基础的双指针和从后往前填充的思路往后面看马上要进入栈与队列、二叉树这些重头戏。所以part2的角色其实是一个承上启下的衔接段——把字符串操作从傻乎乎地遍历提升到有策略地处理同时引入字符串匹配这个新维度为后面那些需要模式匹配的场景做铺垫。1.1 从part1到part2的进阶逻辑part1的三道题344反转字符串、541反转字符串II、卡码网54替换数字核心都在教一件事原地操作时怎么控制指针。那时候你只需要记住左指针、右指针相向而行从后往前填充避免覆盖这些套路就够了。但part2的题目一上来就打破了这个舒适区。151题反转字符串里的单词表面上看是反转但如果你真拿part1那种整体反转一下的思路去套反转完单词内部的字母顺序也乱了根本不对。它逼着你思考一个更复杂的问题怎么在整体操作里保住局部结构的正确性。这个思维链条其实很典型先整体反转再对每个单词做局部反转两次操作叠加之后单词内部顺序恢复但单词之间的相对顺序却反过来了。这个两步反转的技巧在后面旋转数组、旋转字符串的题目里还会出现甚至在链表反转相关的题目里也有类似的影子。我自己的体会是part2不是让你多背几道题的答案而是让你意识到操作顺序本身就是一种算法设计手段。1.2 四道题的考频与核心考点day09字符串part2的完整题目阵容通常包含下面几道不同版本可能会有微调但核心就是这几道题号题目核心考点面试考频LeetCode 151反转字符串中的单词双指针去除多余空格 局部反转极高几乎是字符串类题目的必刷题卡码网 55右旋字符串反转的灵活运用、取模运算中高常作为151题的变种出现LeetCode 28找出字符串中第一个匹配项的下标KMP算法、next数组高KMP是面试常客LeetCode 459重复的子字符串KMP的next数组性质推导中但思路非常巧妙看到没part2的关键词已经变成了匹配和推导——KMP算法是这一天的重头戏也是很多人的噩梦。我当年第一次接触KMP的时候把next数组的代码抄了三遍还是看不懂后来干脆自己动手跑了几组用例才真正明白它到底在干嘛。这篇文章后面会专门用一节来讲KMP的推导过程保证你这次能彻底搞懂。2. LeetCode 151反转字符串里的单词先局部反转再整体反转这道题的要求是给定一个字符串逐个反转字符串中的每个单词。比如输入the sky is blue输出应该是blue is sky the。注意输入字符串里可能包含前导空格、尾随空格、单词之间多个空格但输出只需要保留单词间的单个空格。我第一次做这道题的时候第一反应是这还不简单按空格split成数组然后reverse数组再join起来。在Python里确实可以这样但代码随想录的解法更偏C风格要求你在原字符串上操作——这也是面试里经常追问的点如果不允许额外空间你怎么做2.1 为什么不是从后往前拷贝单词很多人的第一直觉是从后往前遍历原字符串遇到一个单词就把它拷贝到一个新字符串的开头。这个思路本身没错而且能正确输出结果但它需要额外开辟一个和原字符串等长的结果数组空间复杂度是O(n)。在原字符串上操作的解法空间复杂度能做到O(1)。核心思路分三步先去掉字符串里多余的空格前导、尾随、单词间多余空格全去掉让字符串变成单词之间只有一个空格的干净状态把整个字符串反转这时候单词内部字母顺序也反了单词顺序也反了再把每个单词内部做一次反转恢复单词内部的字母顺序。你会注意到第二步之后单词顺序已经正确了但单词内部的字母全倒着第三步就是把它们一个个掰回来。两步反转最终效果正好是单词顺序反转、单词内部不变——这是整道题最精妙的地方。2.2 删除多余空格的双指针细节第一步去空格看起来最简单实际最容易写错。很多人会直接用erase一个字符然后移动后面的所有字符这样时间复杂度就变成了O(n²)。正确做法是双指针定义一个慢指针slow指向新字符串要写入的位置一个快指针fast遍历原字符串fast遇到空格时跳过遇到非空格就把字符复制到slow位置slow前进但要注意每个单词之间需要留一个空格。我习惯的做法是在slow 0即已经写入过内容时先补一个空格再开始拷贝单词。代码如下void removeExtraSpaces(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); }这段代码有个细节值得注意if (slow ! 0) s[slow] 这一行保证了除了第一个单词之外每个新单词前面都会插入一个空格。有些实现会先统一去掉所有空格再把单词拼起来那样反而容易搞混位置关系不如这个边扫描边写的版本直观。2.3 翻转步骤与代码落地第二步和第三步都需要一个反转函数。代码随想录里给的反转函数是左闭右闭区间void reverse(string s, int start, int end) { while (start end) { swap(s[start], s[end]); start; end--; } }注意是左闭右闭end指向最后一个要反转的字符。如果你习惯用左闭右开end指向最后一个字符的下一个位置那调用的时候就要小心别把边界写错了这是我实际刷题时踩过的坑。第三步逐个反转单词需要遍历整个字符串每当遇到空格或者到达字符串末尾就说明一个单词结束了对这个单词区间做一次反转int start 0; for (int i 0; i s.size(); i) { if (i s.size() || s[i] ) { // 到达末尾或空格前一个单词结束 reverse(s, start, i - 1); start i 1; } }这里i s.size()的判断很关键——如果不取等号最后一个单词永远不会被反转。我第一次写的时候用的i s.size()结果最后一个单词一直是反的排查了半天才发现是边界的问题。合起来主函数就是三步string reverseWords(string s) { removeExtraSpaces(s); // 1. 去掉多余空格 reverse(s, 0, s.size() - 1); // 2. 整体反转 int start 0; for (int i 0; i s.size(); i) { if (i s.size() || s[i] ) { reverse(s, start, i - 1); // 3. 逐个单词反转 start i 1; } } return s; }我建议你自己拿 hello world 这个例子手推一遍把每一步的字符串状态写出来比我在这里贴一万个字都管用。手推之后你才会发现原来去掉多余空格之后字符串变短了后续反转的区间边界全都是建立在压缩后的基础上计算的这恰恰是很多人容易搞混的地方。3. 卡码网55右旋字符串反转操作的灵活运用先看一下题目字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。比如abcdefg右旋2位结果就是fgabcde。给定一个字符串s和一个正整数k输出右旋k位之后的字符串。这道题其实原封不动地对应着反转字符串的进阶用法也是力扣189题旋转数组的字符串版。代码随想录里把它放在了part2因为它的解题思路和151题高度一致——又是用两次反转来调整顺序。3.1 右旋的定义与暴力思路先做一步简单的数学转化。右旋k位等价于把字符串分成两部分前n - k个字符n是字符串长度和后k个字符。旋转之后后k个字符跑到前面前n - k个字符整体平移到后面。如果用最暴力的做法开一个新数组先把后k个字符放进去再把前n-k个字符放进去一遍遍历就能搞定。但这样空间复杂度是O(n)而且没有用到任何反转的技巧在面试里显得很没有技术含量。3.2 三次反转的推导过程三次反转的正确思路是这样的先反转整个字符串。abcdefg变成gfedcba反转前k个字符也就是原来字符串最后k个字符所在的位置。前k个现在是gf反转后变成fg此时字符串变成fgedcba反转剩下的字符从第k1个到末尾。edcba反转后变成abcde最终结果就是fgabcde。为什么这样能行核心逻辑在于第一次整体反转让前后两部分的位置对调了但每部分内部的顺序是反的后面两次局部反转分别把每部分内部的顺序掰回来。这和151题先整体反转再局部反转的思路一模一样区别只在于151题需要先去掉多余空格而这道题直接切分即可。3.3 边界条件与输入输出细节这道题在卡码网上是ACM模式需要自己处理输入。输入格式是两行第一行是k第二行是字符串s。我在实际提交时踩过一个坑k可能大于字符串长度。比如字符串长度是7k给的是10那右旋10位其实等价于右旋10 % 7 3位。如果你不取模反转前k个字符这一步就会越界。所以处理输入之后第一步一定要做k k % s.size()。完整的代码如下#include iostream #include string #include algorithm using namespace std; int main() { int k; string s; cin k s; k k % s.size(); // 关键取模处理k大于长度的情况 reverse(s.begin(), s.end()); reverse(s.begin(), s.begin() k); reverse(s.begin() k, s.end()); cout s endl; return 0; }这里我用的是STL的reverse迭代器版本vector和string都适用。如果你在力扣上写类似的旋转字符串题目注意力扣接口用的是下标区间STL用的是迭代器区间别混了。从这道题里我学到的通用套路是任何要求把序列的一段移动到另一端的问题都可以先想想能不能用整体反转 局部反转的组合来实现。这个套路不仅适用于字符串数组旋转、链表旋转同样适用。4. KMP算法LeetCode 28题彻底搞清楚next数组在字符串part2里最硬核的知识点就是KMP算法。LeetCode 28题——找出字符串中第一个匹配项的下标是KMP的标准应用场景。题目本身是在 haystack 字符串里找到 needle 字符串第一次出现的下标不存在则返回-1。很多人一看到KMP就头大包括我自己当年也是。这里我尝试用最直白的语言讲清楚KMP到底解决了什么问题next数组到底是个什么东西。4.1 暴力匹配的痛点暴力匹配的思路是从haystack的第0个位置开始逐个和needle比较一旦发现不匹配就把haystack的指针回退到这次匹配的起点1needle的指针回退到0重新开始匹配。最坏情况是什么比如haystack aaaaabneedle aaab。每次都要比到第4个字符才发现不匹配然后指针回退一大截白白浪费了很多已经比较过、明明可以复用的信息。KMP的聪明之处在于当遇到不匹配的字符时不把needle的指针彻底回退到0而是回退到一个合适的位置让已经匹配过的前缀继续利用起来。而这个合适的位置就是next数组告诉我们的。4.2 next数组到底在记录什么next数组的每个值next[i]表示的是在needle字符串中以第i个字符结尾的子串里最长的相同前后缀的长度。什么叫相同前后缀举个例子aabaaf这个字符串字符串aa的前缀有a后缀有a相同最长相同前后缀长度是1字符串aab的前缀有a、aa后缀有b、ab没有相同的长度是0字符串aabaaf的前缀有a、aa、aab、aaba、aabaa后缀有f、af、aaf、baaf、abaaf相同的前后缀只可能是a注意aa对不上af长度是1。next数组里存的就是每个位置对应的这个值。它为什么有用因为当匹配失败时我们已经知道needle的前j个字符和haystack的某一段匹配上了那么这个前缀里如果有相同前后缀就说明后边这一截和前面那一截是一样的我们不需要重新从needle的第0位开始而是可以从next[j-1]这个位置继续。4.3 构建next数组的代码与手算验证构建next数组的常见写法如下这里采用代码随想录里前缀表不减一的版本void getNext(vectorint next, const string s) { int j 0; next[0] 0; for (int i 1; i s.size(); i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; // 回退 } if (s[i] s[j]) { j; } next[i] j; } }很多人第一次看这段代码都懵了尤其是while (j 0 s[i] ! s[j]) j next[j - 1]这一行。我用aabaaf手算一遍i 1s[1] as[j0] a相等j变成1next[1] 1i 2s[2] bs[j1] a不相等j next[0] 0s[2]b和s[0]a还不相等退出循环next[2] 0i 3s[3] as[j0] a相等j变成1next[3] 1i 4s[4] as[j1] a相等j变成2next[4] 2i 5s[5] fs[j2] b不相等j next[1] 1s[5]f和s[1]a不相等j next[0] 0退出循环next[5] 0。最后next数组是[0, 1, 0, 1, 2, 0]。你可以拿这个数组和任何教程上的结果对一下应该完全一致。回退的那一行j next[j-1]是理解KMP的关键。它做的事情是当前缀匹配不上了就去找更短一点的相同前后缀长度而不是直接从0开始。这就像查字典的时候一个词条找不到不是翻回第一页重新找而是翻到上一次标记的位置继续往后找。4.4 匹配过程的细节有了next数组匹配就好写了int strStr(string haystack, string needle) { if (needle.size() 0) return 0; vectorint next(needle.size()); getNext(next, needle); int j 0; for (int i 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) { j next[j - 1]; } if (haystack[i] needle[j]) { j; } if (j needle.size()) { return i - needle.size() 1; } } return -1; }注意匹配时haystack[i] needle[j]这个条件j指向当前要比较的needle字符。当j等于needle长度时说明整个needle都匹配上了此时i指向的是匹配段最后一个字符起始位置就是i - needle.size() 1。这里还有一个容易踩的坑如果needle的长度为0按题目要求应该返回0。很多人在处理边界时容易遗漏这个特判。5. LeetCode 459重复的子字符串KMP的性质推导这道题的题干很短给定一个非空的字符串s检查是否可以通过由它的一个子串重复多次构成。比如abab可以由ab重复两次构成abcabcabc可以由abc重复三次构成。如果没有KMP的知识这道题用暴力也能做但KMP提供了一个非常优雅的解法关键在于next数组的一个隐藏性质。5.1 判断思路为什么可以用next数组推导过程可以这样理解如果一个字符串 s 是由某个子串 t 重复多次构成的比如s t t ... t那么字符串 s 的最长相同前后缀的长度一定等于s.size() - t.size()。换句话说s的长度减去最长相同前后缀的长度得到的就是那个最小重复单元的长度。如果这个长度能被s的长度整除就说明s可以分成整数个这样的单元。我举个例子s ababab它的前缀有a、ab、aba、abab、ababa后缀有b、ab、bab、abab、babab最长相同前后缀是abab长度4s.size() - 4 2恰好是ab的长度而且6 % 2 0所以确实是由ab重复构成的。再看一个反例s aba最长相同前后缀是a长度1s.size() - 1 2但3 % 2 ! 0所以不能由某个子串重复构成。5.2 找到最小重复单位的数学条件所以判断条件就两步求出next数组取next[s.size() - 1]也就是整个字符串的最长相同前后缀长度记为len判断len 0 s.size() % (s.size() - len) 0。为什么这里要求len 0如果len 0说明整个字符串没有任何相同前后缀那s.size() - len s.size()此时s.size() % s.size() 0恒成立直接把所有字符串都判断成true了这肯定不对。所以要额外加一个len 0的条件。代码写出来很简短bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n); getNext(next, s); int len next[n - 1]; if (len 0 n % (n - len) 0) { return true; } return false; }5.3 两道KMP题对比与常见误区28题和459题都用到了next数组但用法完全不同对比维度28题459题next数组作用匹配失败时确定回退位置计算最长相同前后缀长度核心操作遍历主串用next控制模式串指针直接读取next末尾值做数学判断易错点边界遍历、needle空串特判忘记加len0条件很多人在459题上犯的错误是把next数组一个个打印出来然后用肉眼判断是否对称或者是否有规律。其实完全没必要直接用n % (n - len)这个数学条件判断就可以了。这个推导过程虽然短但是可以反复讲给面试官听是个很好的加分点。6. 刷完这天的题目之后的复盘常犯错误与提速心得day09字符串part2这四道题说多不多说少不少但每一道都值得缝缝补补地刷上两三遍。我在这里整理几个自己反复踩过的坑以及一些可以复用到后续题目的方法论。6.1 我在三刷时才真正理解的几个点第一个是**移除空格双指针里的补空格时机**。我第一次写removeExtraSpaces时把补空格放在了while循环后面结果每个单词后面都跟了一个多余空格。后来才想明白补空格的时机应该是在开始拷贝一个新单词之前而不是拷贝完一个单词之后。这个顺序反了结果完全不一样。第二个是KMP的next数组到底要不要整体减一。网上有两种流派一种是把next数组整体减一[0,1,0,1,2,0]变成[-1,0,-1,0,1,-1]另一种不减一。代码随想录里的写法是不减一的匹配的时候用j next[j-1]回退。这两种写法在逻辑上等价但如果你看别的教程看到减一版本别觉得是错的只是风格不同。我自己建议选定一种刷题时别换不然每次都容易把自己绕晕。第三个是**反转区间的边界计算**。151题和55题都涉及反转区间的确定我的经验是每次反转前先明确这个区间里第一个字符的下标和最后一个字符的下标再调用reverse函数。不要在代码里临时算边界很容易错。6.2 对后面的二叉树、动态规划刷题有什么影响有人可能会问字符串的KMP和二叉树有什么关系关系太大了。KMP里next数组的构建过程本质上是一种**利用已计算的结果来推导新结果的动态规划**——next[i]的值依赖于之前next[j-1]的值而不是重新从头扫描一遍。这种思想在后面刷动态规划题目的时候会反复出现比如最长公共子序列、编辑距离都是用一个数组记录之前的状态遇到不匹配时回到之前某个状态。另外151题里先整体操作再局部操作的思路在二叉树里也有对应——比如翻转二叉树先交换左右子树再递归处理子树内部其实也是一种先整体后局部。刷字符串题目时养成的这种操作顺序设计的习惯会在后面的数据结构题目里潜移默化地帮到你。6.3 给刚开始刷字符串题目的人的建议如果你现在刚刷到day09正在被KMP折磨我给你几个具体建议第一不要只看不写。KMP这个东西看十遍不如手推一遍。拿一个短的字符串比如aabaaf自己在纸上把next数组的每个值推导一遍然后再跟着代码走一遍你会发现之前看不懂的那些while循环突然就顺了。第二把151题的反转函数封装好后面会一直用。不管是右旋字符串、旋转数组还是某些链表题反转操作的出现频率比你想象的高。提前写好一个通用的reverse函数能省很多事。第三刷完之后隔几天再回头做一遍。我个人经验是字符串题目特别容易当时看懂、两天就忘。最好的办法是当天刷完后第二天把四道题的代码默写一遍不用一模一样能推出正确思路就行。这样坚持几天这些套路才会真正长在脑子里。最后再提醒一句字符串part2的题目在面试里非常高频。151题和28题基本是很多公司算法面试的标配459题的KMP推导也经常作为追问出现。所以这一天的内容值得你多花点时间一步一个脚印地吃透。刷题这件事最忌讳的就是看起来很努力——题目数量刷得再多不如把每道题背后的思维模式真正搞明白。