字符串这个专题是代码随想录系列里让我觉得最典型的一个“看起来简单动起手来全是坑”的部分。第八天专门腾出来过字符串主要围绕反转字符串、替换空格、翻转单词、左旋转字符串和KMP匹配展开。如果你正在备战算法面试这天的内容基本把字符串题型里最高频的几个套路都覆盖了适合从零开始系统性刷题的人也适合已经刷过一部分、但总在边界条件上翻车的同学。先说一个整体感觉字符串题本身不难难在三个地方——语言特性不熟、边界条件容易漏、KMP这种偏底层的算法需要额外花时间消化。第八天的安排其实是在帮你把“字符串题”从一堆零散题目里收敛成几个可复用模板刷完之后你会发现很多中等题其实都是“反转 双指针 KMP”这几个套路在排列组合。1. 字符串题目的底子先分清三件事1.1 字符串到底是不是数组很多人在字符串题里一开始就写错原因是没搞清语言里字符串的存储方式。在 C 里string本质上是一个可变长度的字符数组可以直接用下标访问和修改比如s[0] a是合法的。但在 JavaScript 和 Python 里字符串是“不可变”的s[0] a这行代码不会生效甚至会直接报错或者静默失败。这两个阵营的做题思路完全不同处理 C 字符串时可以先当成数组原地操作空间复杂度能做到 O(1)。处理 JavaScript / Python 字符串时通常要先split()转成数组操作完再join()转回字符串。我当时在 JavaScript 里写反转字符串第一版直接写s[left] s[right]结果发现字符串根本没变排查了半天才意识到是不可变的问题。后来就养成了习惯凡是涉及原地修改字符串的题目先判断语言特性再决定要不要转数组。1.2 语言层面的字符串坑一次说清楚除了不可变问题这些年我在实际练习里碰到的高频语言坑还包括字符串比较Java 里比较的是引用equals()才是比较内容JavaScript 里偶尔会因为隐式转换带来迷惑所以判断相等尽量用。字符串转数字parseInt、Number、Number() 字符串看起来差不多但遇到空字符串、小数、特殊字符时结果完全不同刷题时尤其容易埋坑。C 风格字符串C 语言里字符串本质是char数组以\0结尾一旦忘记预留结尾位置很容易越界访问。模板字符串JavaScript 里用反引号拼接字符串确实方便但面试手写算法时别依赖这些语法糖因为换个环境可能就不支持了。这些看着是“基础语法”但在紧张环境下写代码往往就是这些细节决定一遍能不能过。所以我的建议是第一天先把每种语言里字符串的增删改查都写一遍别急着刷题。2. 反转字符串双指针怎么打2.1 最朴素的整体反转模板反转字符串是整个专题的入门第一题也是最标准的双指针模板。思路很简单一个指针从最左边走一个指针从最右边走两边同时交换字符直到两个指针相遇。在 C 里可以直接这样写void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } }如果不用swap手动交换也行但要注意别写反了char temp s[left]; s[left] s[right]; s[right] temp;在 JavaScript 里因为字符串不可变我会这么写function reverseString(s) { let arr s.split(); let left 0, right arr.length - 1; while (left right) { [arr[left], arr[right]] [arr[right], arr[left]]; left; right--; } return arr.join(); }这里最容易错的地方是循环条件。写while (left right)也能跑但对偶数长度的字符串最后会出现一次多余的自我交换虽然结果不影响不过从算法严谨性看left right才是正确写法。2.2 按步长反转小心尾巴整体反转学会之后马上会碰到一道进阶题给定一个字符串每隔2k个字符反转前k个字符如果剩余字符少于k个就把剩余全部反转如果剩余字符在k到2k之间只反转前k个。这种题核心是搞清楚遍历步长不是每次都走一格而是走2kfunction reverseStr(s, k) { let arr s.split(); for (let i 0; i arr.length; i 2 * k) { let left i; let right Math.min(i k - 1, arr.length - 1); while (left right) { [arr[left], arr[right]] [arr[right], arr[left]]; left; right--; } } return arr.join(); }关键点在于right Math.min(i k - 1, arr.length - 1)。这是这道题最容易错的地方——如果直接让right i k - 1当最后一段字符数不够时下标会越界。我当时第一次写的时候觉得“反转区间边界”很简单结果提交后连续报错打印中间结果才发现是尾巴上的下标问题。这种题的价值不在于难度而是训练你对“区间边界”的敏感度。后面很多中等题其实都是在这些基础边界上叠加更多条件。2.3 双指针为什么能保证 O(1) 额外空间做字符串反转的时候经常听到“原地算法”这个词。它要求的不是把字符串复制一份再反转而是在原字符串上直接交换。双指针方案的优势正在于此只占用常数级别的额外空间时间复杂度是 O(n)每个字符最多被交换一次。这个思想在面试里很加分。尤其是当你用 JavaScript 写的时候如果直接s.split().reverse().join()虽然一行就搞定但面试官通常会追问一句“你能否不用额外空间”所以平时练习还是建议手写双指针把原地交换练出肌肉记忆而不是依赖语言自带的reverse方法。3. 替换空格从后往前填避免污染3.1 先数空格再扩容替换空格是字符串题里很经典的一道把字符串中的每个空格替换成%20。最直观的想法是遍历字符串遇到空格就替换但问题是替换后的字符串长度变长了直接原地插入会导致后面的字符被覆盖。正确做法分两步先遍历一遍字符串统计空格数量。根据空格数量计算新字符串长度将原字符串扩容到新长度。用两个指针从后往前遍历一个指针指向旧字符串末尾一个指针指向新字符串末尾一步步把字符复制到新位置遇到空格就依次填入%、2、0。C 代码参考string replaceSpace(string s) { int oldLen s.size(); int count 0; for (char c : s) { if (c ) count; } s.resize(oldLen count * 2); int newLen s.size(); for (int i oldLen - 1, j newLen - 1; i 0; i--, j--) { if (s[i] ) { s[j] 0; s[j - 1] 2; s[j - 2] %; j - 2; } else { s[j] s[i]; } } return s; }3.2 为什么必须从后往前很多人第一次做这道题时会习惯性地从前往后遍历然后发现插入一个%20就要把后面的所有字符都往后挪一位整体复杂度直接变成 O(n²)。从后往前填的好处是每个字符只需要移动一次整体是 O(n)。这个思路可以类比成“排队的时候让人整体挪位置”。如果你从队伍前面开始往后插队后面每个人都要动如果你先把所有人往后腾好位置再从末尾一个个安排进去每人只需要移动一次。另外有个小细节j - 2这行很容易漏。因为循环体末尾还有一个j--所以如果遇到空格在完成三个字符填充后j需要额外减 2才能让下一次循环的j指向正确位置。我见过很多人在这一步卡住调试半天。其实只要在纸上画一遍两个指针的移动过程就清楚了。4. 整体反转局部反转单词翻转的通用套路4.1 翻转单词三步法字符串题里翻转单词是另一个高频考点比如把the sky is blue变成blue is sky the。这道题要是不动脑筋很多人会直接用split和reversefunction reverseWords(s) { return s.trim().split(/\s/).reverse().join( ); }写出来确实简单但面试时这么写往往不够。面试官更希望看到你能解释清楚“为什么这一步先做、那一步后做”并且能处理多余空格的情况。手动实现的核心套路就三步移除多余空格保证单词之间只有一个空格开头和结尾没有空格。对整串字符做整体反转此时单词顺序颠倒但单词内部字母顺序也反了。对每个单词再做一次局部反转把单词内部的字母顺序恢复正常。比如the sky is blue整体反转后变成eulb si yks eht对 4 个单词分别反转得到blue is sky the。这个三步法很重要因为“左旋转字符串”这类看似不同的题目本质上也是同一个套路。4.2 左旋转字符串本质是一样的思路左旋转字符串的题目描述通常是把字符串前面的若干个字符转移到字符串的尾部比如abcdefg左旋 2 位得到cdefgab。最直接的方式是切片function reverseLeftWords(s, n) { return s.slice(n) s.slice(0, n); }但如果不让用切片可以用“局部反转 整体反转”完成反转前 n 个字符abcdefg的前 2 个反转后变成bacdefg反转后面的字符剩下cdefg反转后变成bagfedc整体反转得到cdefgab。代码示例function reverseLeftWords(s, n) { let arr s.split(); reverse(arr, 0, n - 1); reverse(arr, n, arr.length - 1); reverse(arr, 0, arr.length - 1); return arr.join(); } function reverse(arr, left, right) { while (left right) { [arr[left], arr[right]] [arr[right], arr[left]]; left; right--; } }做完这两类题之后你会发现字符串题里很多所谓的“新题”都是在考你有没有掌握“先整体、后局部”这种两个基本操作的组合。只要能熟练写出reverse这个子函数很多题都会变得很顺。5. KMP字符串匹配的重武器5.1 暴力匹配为什么慢字符串题里最让人头疼的大概率是 KMP。它解决的场景很简单给定一个文本串haystack和一个模式串needle找出模式串在文本串中第一次出现的位置。暴力解法是每次从文本串的一个位置开始和模式串逐位比较失败就右移一位重新从头比较。这看起来没什么问题但最坏情况下时间复杂度是 O(n × m)比如文本串是aaaaaaaaab模式串是aaaab每次失败后都要回到模式串开头做了大量重复比较。KMP 的核心思想是当某一位匹配失败时不是单纯回到起点重新来而是利用已经匹配过的部分跳过那些不可能匹配的位置。这个“跳过”的关键就落在next数组上。5.2 next 数组到底存什么next数组做的是件事对模式串的每个位置算出它前面这段子串的“最长相等前后缀长度”。这里先解释以下“前缀”和“后缀”前缀从第一个字符开始但不包含最后一个字符的所有子串。后缀到最后一个字符结束但不包含第一个字符的所有子串。最长相等前后缀前缀集合和后缀集合里长度最大且内容相同的那个。比如模式串aabaaab不同前缀位置的最长相等前后缀长度就是后面计算next的依据。理解这个比死记代码更重要。打个比方这就像你做题时准备的错题本错一次之后下次看到类似题型就知道不需要每一步都重新推理直接跳到上次卡住的位置继续。5.3 手写一份 next 数组构建代码next数组的构建是 KMP 里最劝退的地方因为网上的写法有好几种有的直接存最长相等前后缀长度有的整体减一有的整体右移一位。初学者看多了容易混。我建议你只要掌握一种最直观的写法就好next[i]表示以i结尾的子串中最长相等前后缀的长度。JavaScript 版构建next数组function getNext(pattern) { let next new Array(pattern.length).fill(0); let j 0; for (let i 1; i pattern.length; i) { while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; } if (pattern[i] pattern[j]) { j; } next[i] j; } return next; }这段代码里最关键的是while循环里的j next[j - 1]。很多人在手写时容易忘掉它结果遇到前缀后缀不匹配的情况就死循环。理解方式是当前不匹配时不能直接把j清零而是让j回退到前一个位置的next值利用已经算好的信息继续比较。拿到next数组后匹配过程就是同样的思路function strStr(haystack, needle) { if (needle.length 0) return 0; let next getNext(needle); let j 0; for (let i 0; i haystack.length; i) { while (j 0 haystack[i] ! needle[j]) { j next[j - 1]; } if (haystack[i] needle[j]) { j; } if (j needle.length) { return i - j 1; } } return -1; }KMP 在一个讨论字符串的专题里占的篇幅不短但我个人觉得如果面试不是明确要求写 KMP很多场景下暴力匹配已经够用。不过理解 KMP 的过程对手写字符串算法能力的提升很大尤其是“利用已匹配信息减少回退”的思想在做重复子字符串判断、正则表达式相关问题时都有迁移价值。6. 常见坑和调试清单6.1 我踩过的坑字符串刷到第八天我踩过的坑基本可以总结成这么几类边界下标出错。反转区间时right忘了取最小值导致数组越界。这是出现频率最高的错误没有之一。while 条件写错。反转时写成left right虽然结果往往碰巧正确但在某些特殊用例下会多一次操作KMP 里忘记j next[j-1]直接表现就是死循环。语言特性记错。JavaScript 里字符串不可变却直接给某个下标赋值Java 里用比较字符串内容。空格处理不干净。翻转单词时用split( )会把连续空格变成空字符串项结果拼接回来多出一堆空格。之后我习惯先用trim()去掉首尾空格再按连续空白字符切分。C/C 的字符和字符串混淆。char只能用单引号字符串用双引号写%20这种就是错的应该拆成三个char字符分别赋值。6.2 一组值得跑的测试用例刷完字符串专题后我每次写完都会跑下面这组用例能覆盖大部分边界情况用例输入期望结果主要考察点空字符串代码是否直接崩溃单字符aa反转循环是否进入双字符abba偶数长度的边界奇数字符abccba中间字符是否被正确保留连续空格a bb a多余空格是否被移除Unicode/中文中文按题目逻辑验证字符编码是否会破坏算法重复前缀后缀ababab可测 KMP 是否死循环回退逻辑是否正确超长字符串10 万字符能正常结束是否有 O(n²) 退化这套用例不需要全部手动敲但至少空串、单字符、重复模式这几个一定要测。KMP 相关的题目多跑几组a、aa、aaa这类模式串能发现大量想当然的问题。6.3 别忽略调试输出我在练字符串题时会习惯性地打印中间结果尤其是反转区间和next数组的值。比如 KMP 里的next数组手动计算一次aabaaab的next再对比代码输出很快就能发现逻辑差异。很多讲解喜欢直接把next数组的表格贴出来但只有自己手写一遍、打一遍日志才能真正理解它的构造过程。7. 第八天之后怎么继续练第八天的内容练完之后我的体会是字符串题最重要的是形成肌肉记忆。反转、替换、翻转单词、KMP 这些模板最好都能在不看资料的情况下手写出来而且至少会两种语言版本。这样面试时不管面试官用的是在线编辑器还是白板你都不会因为某个语法细节卡壳。另外建议把字符串专题里的题按类型归个类。我自己分类的方式是反转类整体反转、按步长反转、局部反转组合。替换类空格替换、字符替换、数字格式化。匹配类暴力匹配、KMP、重复子串判断。语言特性类比较相等、转数字、拼接、模板字符串。每类各写两三道题再多做一遍错题基本就能应付常见的字符串面试题了。