字符串这东西刷题前觉得“不就是字符数组嘛”刷题后才发现它才是算法面试里的“隐形大头”。算法训练营Day8这一天正好把字符串Part01系统过了一遍反转字符串、反转字符串II、替换空格、翻转字符串里的单词、左旋转字符串清一色高频题。这篇就当一天的复盘笔记把思路、代码、坑位一次说透给还在字符串门口打转的朋友一个可直接照抄的路线。适合谁看准备面试的、刚刷完数组想进入字符串的、或者刷过几道但总是死在边界条件上的都可以对照着过一遍。我尽量用大白话把每一步讲明白顺便把当年踩过的坑标出来免得你重走弯路。1. 字符串在算法体系中的定位与学习路径设计1.1 为什么单独拿一整天讲字符串很多人觉得字符串简单无非是遍历、比较、拼接。但真正刷起来才发现字符串是“数组的进阶版”它既保留了数组的随机访问特性又叠加了字符编码、不可变性、拼接性能这些额外约束所以面试官特别爱在字符串题目里藏边界条件。训练营把字符串拆成Part01和Part02是有讲究的。Part01聚焦“基础操作”原地修改、双指针、整体翻转、局部翻转这些都是后面KMP、滑动窗口、回文串等高级算法的基础。如果Part01的地基没打牢后面学KMP的next数组、学最长回文子串的动态规划会学得怀疑人生。另外字符串在真实工作里出现频率极高。无论是写解析器、处理用户输入、做敏感信息脱敏还是写接口层的参数校验每天都会碰字符串。从面试角度说字符串题往往能在一道题里同时考察“编码习惯”“边界思维”“复杂度意识”三个维度性价比非常高。1.2 不同语言里字符串的底层差异是新手栽跟头的第一站同样一道字符串题用C写和用Java写、用Python写处理方式完全不一样。这里必须先把语言差异讲清楚否则你会发现“我明明按照题解写的怎么就是不对”。C里的std::string是可变对象底层是一段连续内存本质上是字符数组的封装所以可以像数组一样通过下标随机访问也可以原地修改。C风格的字符串则以\0结尾面试中如果遇到C语言风格的字符串题比如“字符串逆序输出c”这种纯C写法必须手动维护结尾标志。Java的String是不可变对象每次拼接、替换都会生成新对象所以在Java里做字符串原地修改一般要转成char[]或StringBuilder。这是新手特别容易踩的坑在Java里用String做循环拼接时间复杂度会退化到O(n²)因为每一次都会新建字符串对象。Python的str同样是不可变对象而且Python没有“字符数组”的概念字符串反转最方便的是切片[::-1]但切片会生成新字符串。如果面试官要求“原地修改”Python就比较尴尬通常要转成list操作再转回字符串。刷题时我建议先选定一门主语言把思路跑通再用其他语言验证一下对语言特性的理解。比如训练营里同一个小伙伴用C写反转字符串直接用swap即可我用Java写就得先toCharArray()转数组再交换字符最后new String(chars)转回字符串。语言差异不是算法的核心但它是你写出“能跑的代码”的第一道门槛。注意算法训练营里我踩过最大的一个坑就是用Java的String直接做大量拼接然后超时。刷题之前先确认你的主语言对字符串的操作是不是原地修改这一点能省下一整晚的调试时间。2. 字符串题目实战5道经典题从暴力到优雅2.1 反转字符串344双指针的入门教学这道题虽然简单但它是字符串双指针思想的“第一课”。题目要求输入一个字符数组原地反转不能额外开辟空间。暴力做法是新建一个等长数组倒序放进去。但面试官要的是原地修改这时候双指针就是最优解左指针从数组头出发右指针从数组尾出发交换两个指针指向的字符然后左指针右移、右指针左移直到两个指针相遇。class Solution { public: void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } };如果有Java基础注意要先转成char[]Python的话虽然可以一行return s[::-1]但如果面试要求原地最好转成list然后左右交换。为什么双指针是最优解因为它只遍历一次时间复杂度O(n)空间复杂度O(1)。你可能会想“难道不能从中间开始往两边交换吗”当然可以但中间向两边的写法对奇数长度和偶数长度的处理更麻烦不如左右对撞简单直观。这道题我特别建议自己手写一遍不是为了“会写”而是为了体验“while (left right)”这个条件的推导过程。很多人第一次写会写成while (left ! right)当字符数组长度是偶数时最终left会越过right永远不等导致死循环或越界。left right才是严谨的写法。2.2 反转字符串II541需求理解是最大考点这道题是反转字符串的变种但难度陡增因为它加入了“每计数2k个字符就反转前k个字符”的规则。题目要求是这样的每计数至2k个字符就反转这2k个字符中的前k个字符。如果剩余字符少于k个则将剩余字符全部反转。如果剩余字符大于或等于k个但小于2k个则反转前k个字符其余字符保持原样。我第一次做这道题时直接用了一堆if-else去模拟结果写了一堆bug。后来发现更优雅的方式是让for循环的步长直接设为2k这样每次循环天然处在一个“2k区间”的起点。class Solution { public: string reverseStr(string s, int k) { for (int i 0; i s.size(); i 2 * k) { // 剩余字符小于 k反转全部剩余 if (i k s.size()) { reverse(s.begin() i, s.end()); } else { // 剩余字符大于等于 k反转前 k 个 reverse(s.begin() i, s.begin() i k); } } return s; } };这段代码的思路核心在于“步长为2k”自动把字符串切成了若干个长度为2k的区间每个区间只需要判断“当前位置加上k是否超过字符串长度”。如果超过说明剩余不足k个全反转否则反转前k个。两个分支覆盖了题目所有规则。这里最值得品的是为什么用i 2 * k而不是i。如果老老实实模拟“计数到2k才反转”你得在循环里维护一个计数器代码会复杂很多。而把步长设为2k就让每次循环都站在一个区间的开头问题就简化成了“当前区间内够不够k个”。2.3 替换空格剑指Offer 05从后往前填充的经典思路题目要求把字符串中的每个空格替换成“%20”。这道题在训练营里被我们称为“从后往前填充”思想的启蒙题因为如果从前往后替换每次替换都要把后面的字符整体后移时间复杂度会退化成O(n²)。正确的做法分两步先遍历一遍原字符串统计空格数量计算出新字符串的总长度。假设原长度为len空格数为count新长度为len 2 * count因为一个空格从1个字符变成3个字符净增2个字符。从后往前填充原字符串的末尾指针指向原长度-1的位置新字符串的末尾指针指向新长度-1的位置。从后往前遍历原字符串遇到普通字符就复制到新末尾遇到空格就在新末尾依次填入“0”、“2”、“%”注意顺序从后往前所以先填0再填2最后填%。class Solution { public: string replaceSpace(string s) { int count 0; for (char c : s) { if (c ) count; } int oldLen s.size(); int newLen oldLen 2 * count; s.resize(newLen); for (int i oldLen - 1, j newLen - 1; i 0; i--) { if (s[i] ) { s[j--] 0; s[j--] 2; s[j--] %; } else { s[j--] s[i]; } } return s; } };为什么从后往前填充是正确做法因为从后往前填充时每个字符最多被移动一次时间复杂度O(n)空间复杂度O(1)假设原字符串可变。这个过程类似于“归并排序的合并阶段从后往前放元素”的思路。一个常见的疑问是为什么不能先申请一个新数组遍历原字符串拼出新结果当然可以但那样空间复杂度是O(n)。在数组类题目里面试官往往要求“原地修改”从后往前填充就是为了满足这个要求而设计的。3. 字符串进阶实战翻转与旋转3.1 翻转字符串里的单词151三步走策略这道题是字符串Part01里综合难度最高的一道它把“移除多余空格”、“整体反转”、“局部反转”三个知识点串在一起。题目要求给定一个字符串逐个翻转字符串中的每个单词同时要去除多余空格。示例输入是the sky is blue输出blue is sky the输入 hello world! 输出world! hello。如果用高级语言自带split比如Python的split()再反转再join几行就搞定了。但面试官通常希望你能手写这个过程考察的是对字符串操作的控制力。标准的解法分三步第一步移除多余空格。这里的“多余”包括字符串开头结尾的空格、单词之间的多个空格。可以用快慢指针实现快指针遍历原字符串当快指针遇到一个单词的起始字符时先把一个空格放到慢指针位置如果慢指针不在开头然后把整个单词复制过去。class Solution { public: string reverseWords(string s) { // 1. 移除多余空格 int slow 0; int n s.size(); for (int fast 0; fast n; fast) { if (s[fast] ! ) { if (slow ! 0) s[slow] ; while (fast n s[fast] ! ) { s[slow] s[fast]; } } } s.resize(slow); // 2. 整体反转 reverse(s.begin(), s.end()); // 3. 逐个单词反转 int start 0; for (int end 0; end s.size(); end) { if (end s.size() || s[end] ) { reverse(s.begin() start, s.begin() end); start end 1; } } return s; } };第二步把整个字符串反转。以the sky is blue为例整体反转后变成eulb si yks eht。这时每个单词的字母顺序是反的但单词之间的相对顺序已经正确。第三步逐个单词反转。遍历字符串遇到空格或到达末尾时把当前单词区间反转单词内部的字母顺序就恢复正确了。此时eulb si yks eht变成blue is sky the恰好是答案。这个“先整体反转再局部反转”的思想特别重要它不仅能解决单词翻转还能解决后面要讲的左旋转字符串。核心逻辑是整体反转解决的“顺序”问题局部反转解决的是“内部顺序”问题两个操作合起来就能完成任意局部顺序的调整。3.2 左旋转字符串剑指Offer 58-II三次反转搞定循环位移题目要求把字符串前面的k个字符转移到字符串末尾。比如输入abcdefgk2输出cdefgab。暴力做法是新建一个字符串先拼后半部分再拼前半部分。但如果要求原地操作就要用到三次反转的思路反转前k个字符。反转k到末尾的字符。反转整个字符串。以abcdefgk2为例反转前2个bacdefg。反转剩余5个bagfedc。整体反转cdefgab。写成代码非常简单class Solution { public: string reverseLeftWords(string s, int n) { reverse(s.begin(), s.begin() n); reverse(s.begin() n, s.end()); reverse(s.begin(), s.end()); return s; } };为什么三次反转能实现左旋本质上字符串左旋转等价于“把前半段和后半段交换位置但各自内部顺序保持不变”。第一次和第二次局部反转让前半段和后半段内部的顺序颠倒第三次整体反转把所有字符的顺序再颠倒一次于是每个段的内部顺序被“负负得正”恢复原样而两段之间的相对位置则完成了交换。这就像把两叠牌各自翻面再把整叠牌翻面最终两叠牌都回到了正面向上但位置互换了。这道题有一个变体右旋转字符串比如LeetCode的“反转字符串中的单词III”和“轮转数组”都有类似思路。如果你理解了三次反转的本质无论左旋还是右旋都能在三分钟内写出来。提示左旋转字符串用substr拼接也能做但面试时最好提一句“原地反转方案”然后动手写三次反转。这能向面试官传递你理解复杂度的信号。4. 字符串高频操作与底层细节从刷题到工程4.1 字符转换、分割与大小写面试常考的API组合拳字符串Part01的算法题背后其实暴露了很多语言API的使用熟练度问题。训练营里我见过不少代码逻辑正确但API用错的案例这里把工程里高频的几类操作统一过一遍。字符串转数字是绝对的高频需求。C里可以用stoi、stol、stoll但要注意它们会抛出invalid_argument和out_of_range异常。Java里是Integer.parseInt和Long.parseLong同样会抛NumberFormatException。真正面试时题目往往不会让你直接调API而是要求手写一个简易的atoi这时候要考虑正负号、前导空格、溢出等问题。这一个考点可以单独出一道中等题很多大厂都出过。字符串分割在工程里更常见。C没有内置的split需要配合istringstream和getline实现Java有String.split但要注意split的参数是正则表达式用.分割时要写成split(\\.)Python的split()则好用很多但也要注意不传参数和传空格的区别。建议手写一个通用的split函数放在自己的代码模板里面试时直接背模板能省不少时间。大小写转换也是常客。C里toupper和tolower接收的是int类型的字符码返回int转成char使用时经常被忽略Java里Character.toUpperCase和Character.toLowerCasePython则是str.upper()和str.lower()。注意C的tolower如果传入的是负数比如扩展ASCII码是未定义行为需要先转成unsigned char再调用。还有一个被很多人忽略的操作获取子串。Java的substring(beginIndex, endIndex)是前闭后开区间Python的切片[start:end]也是前闭后开而C的substr(pos, count)第一个参数是起始位置第二个参数是长度。这三个语言三种语义我用Java写习惯了切到C写substr时就经常把第二个参数写成结束索引结果字符串长度比预期长或短。所有跨语言刷题的人都建议把这三个API的差异贴在显示器上。4.2 调试字符串题的三个实用技巧打印、断言、单步跑字符串题调试起来比数组题烦人因为它输出出来是一长串字符很难一眼看出哪一位错了。我在训练营里摸索出三个技巧能显著减少调试时间。第一个技巧是打印时加辅助标记。不要直接cout s而是把字符一个个输出并在每个字符下标处加上分隔符。比如调试反转字符串时可以打印cout [ i ] s[i] 这样能立刻定位到是哪个下标出了问题。特别是处理“翻转字符串里的单词”时空格在控制台里很难肉眼分辨最好把空格替换成_再打印。第二个技巧是写断言验证不变量。反转字符串时最核心的不变量是“交换后左指针位置的值等于原来的右指针位置的值”。可以在交换之后加一个assert(s[left] oldRightValue s[right] oldLeftValue)如果断言失败说明指针移动顺序写错了。调试字符串题时断言往往比看输出更快。第三个技巧是准备一份“边界测试用例集”。字符串题的边界无非是空字符串、只含空格、首尾有空格、单词之间多个空格、单个字符、全同字符。每道题写完后把这些用例挨个跑一遍基本能覆盖90%的隐藏bug。我在训练营里专门建了一个测试用例清单刷字符串时反复用效率高出不少。5. 常见问题与坑位记录5.1 索引、边界、空串字符串题的三座大山字符串Part01刷完我把周围小伙伴问得最多的问题汇总了一下基本集中在三类第一类是索引越界。C里reverse(s.begin() i, s.begin() i k)如果i k超过s.end()虽然reverse不会崩但行为是未定义的。Java里substring更是直接抛IndexOutOfBoundsException。这类问题的根源在于“区间终点”和“区间长度”的概念没分清。记住一条C的左闭右开区间和Java的substring左闭右开区间终点索引是可以等于末尾的但绝对不能超过末尾。第二类是空串和单字符的特殊处理。很多人在写“翻转字符串里的单词”时都会在end s.size()这个条件上栽跟头。如果字符串本身就是空串resize(0)后for循环条件end s.size()会怎么样此时s.size()为0循环还是会执行一次end 0然后start 1可能越界。所以遇到空串必须提前返回。第三类是C的resize与字符串长度的坑。resize(newLen)会把字符串扩长但扩长后新位置填充的是\0字符。如果你忘了从后往前填充而是从前往后遍历那么遇到\0也会被当作普通字符处理结果就多出不可见字符。这种bug在控制台输出里很难发现但用size()打印长度时立刻露馅。5.2 字符串只是起点KMP与后续学习方向预告字符串Part01看起来只是反转一下、替换一下但它背后延伸出去的算法很多。比如“判断一个字符串是否是另一个字符串的子串”暴力做法是O(n*m)但用KMP算法可以把时间复杂度降到O(nm)。KMP的核心是next数组而next数组的构建过程本质上又是一次字符串匹配问题层层嵌套。再往后很多经典算法都以字符串为基础。比如文本搜索引擎里的BM25算法本质上是计算查询词与文档之间的相似度它需要大量的字符串切分和词频统计规则引擎Drools里的Rete算法虽然核心是模式匹配但匹配的前提也是把规则条件和事实对象转成可比较的字符串特征甚至深度学习里的文本模型第一步也是把文本转换成token序列。字符串处理能力强的人学这些算法会快得多。当然训练营的节奏是一步一步来的。Day8的Part01先把基础操作练扎实Part02就会进入KMP、重复子串判断等内容。建议你把今天的五道题再独立手写一遍不要看题解写不出来就重新看这一篇写出来了再往后走。5.3 一些关于字符串刷题节奏的实战建议最后分享几个我自己调整过的刷题节奏适合那些刷了两天字符串就开始怀疑人生的人。一天不要贪多。字符串Part01的五道题我第一天只做了反转字符串和反转字符串II第二天才做替换空格和翻转字符串里的单词第三天做左旋转字符串并复盘。题目之间质量差异很大比如“翻转字符串里的单词”一道题的思考量顶得上三道简单题给它留足时间完全值得。每道题写完后不要立刻看下一题先做“复杂度三问”时间复杂度是多少空间复杂度是多少如果要优化空间能不能做到O(1)这三个问题在面试时几乎必问平时刷题就当成肌肉记忆来练。如果一道题看了15分钟还是没思路直接看题解但看完题解不要马上抄而是合上题解自己在白纸上复盘一遍思路再动手写。这一步习惯帮我把“看懂了”和“真的会了”区分开。注意字符串题最忌讳“裸写”。哪怕你觉得思路已经烂熟于心也一定先写注释或画一下指针移动的过程。字符串的索引一旦错了调试成本远比数组题高因为字符输出后很难用肉眼定位“谁在哪个位置被改错了”。刷完这一天的内容我最大的感受是字符串里没有太多神秘的数据结构知识它考的就是“你能不能把一件看似简单的事情做到极致细节”。反转字符串人人会写但反转字符串II一加边界条件就刷掉了一批人。这其实也是算法面试的缩影不是比谁懂更多花哨的算法而是比谁能在边界和细节上不出错。我把Day8的题目和易错点全写在这篇里了如果你也刷到了字符串Part01建议跟着这五道题过一遍尤其注意每一次reverse的区间边界。等Part02的KMP出来我再接着写。