企业官网建设流程全解析

字符串这个专题，是代码随想录系列里让我觉得最典型的一个“看起来简单，动起手来全是坑”的部分。第八天专门腾出来过字符串，主要围绕反转字符串、替换空格、翻转单词、左旋转字符串和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(vector<char>& 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个。

这种题核心是搞清楚遍历步长，不是每次都走一格，而是走2k：

function 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。最直观的想法是遍历字符串，遇到空格就替换，但问题是替换后的字符串长度变长了，直接原地插入会导致后面的字符被覆盖。

正确做法分两步：

1. 先遍历一遍字符串，统计空格数量。
2. 根据空格数量计算新字符串长度，将原字符串扩容到新长度。
3. 用两个指针从后往前遍历：一个指针指向旧字符串末尾，一个指针指向新字符串末尾，一步步把字符复制到新位置；遇到空格就依次填入'%'、'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和reverse：

function reverseWords(s) { return s.trim().split(/\s+/).reverse().join(' '); }

写出来确实简单，但面试时这么写往往不够。面试官更希望看到你能解释清楚“为什么这一步先做、那一步后做”，并且能处理多余空格的情况。

手动实现的核心套路就三步：

1. 移除多余空格，保证单词之间只有一个空格，开头和结尾没有空格。
2. 对整串字符做整体反转，此时单词顺序颠倒，但单词内部字母顺序也反了。
3. 对每个单词再做一次局部反转，把单词内部的字母顺序恢复正常。

比如"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); }

但如果不让用切片，可以用“局部反转 + 整体反转”完成：

1. 反转前 n 个字符："abcdefg"的前 2 个反转后变成"bacdefg"；
2. 反转后面的字符：剩下"cdefg"反转后变成"bagfedc"；
3. 整体反转：得到"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 一组值得跑的测试用例

刷完字符串专题后，我每次写完都会跑下面这组用例，能覆盖大部分边界情况：

这套用例不需要全部手动敲，但至少空串、单字符、重复模式这几个一定要测。KMP 相关的题目，多跑几组"a"、"aa"、"aaa"这类模式串，能发现大量想当然的问题。

6.3 别忽略调试输出

我在练字符串题时会习惯性地打印中间结果，尤其是反转区间和next数组的值。比如 KMP 里的next数组，手动计算一次"aabaaab"的next，再对比代码输出，很快就能发现逻辑差异。很多讲解喜欢直接把next数组的表格贴出来，但只有自己手写一遍、打一遍日志，才能真正理解它的构造过程。

7. 第八天之后怎么继续练

第八天的内容练完之后，我的体会是：字符串题最重要的是形成肌肉记忆。反转、替换、翻转单词、KMP 这些模板，最好都能在不看资料的情况下手写出来，而且至少会两种语言版本。这样面试时，不管面试官用的是在线编辑器还是白板，你都不会因为某个语法细节卡壳。

另外，建议把字符串专题里的题按类型归个类。我自己分类的方式是：

• 反转类：整体反转、按步长反转、局部反转组合。
• 替换类：空格替换、字符替换、数字格式化。
• 匹配类：暴力匹配、KMP、重复子串判断。
• 语言特性类：比较相等、转数字、拼接、模板字符串。

每类各写两三道题，再多做一遍错题，基本就能应付常见的字符串面试题了。