1. 内容整体设计与思路拆解1.1 为什么第八天会卡在字符串这道坎上说真的算法训练营走到第九天能坚持下来的同学已经干掉了一批人。前面几天我们啃完了数组、链表、哈希表、双指针这些基础结构到了字符串这一块很多人会误以为字符串不就是字符数组吗有什么好学的。结果一上手做题就懵了——明明思路好像是对的代码写出来却总是越界、反转不到位、拼接顺序反了。这背后的核心原因在于字符串虽然底层是字符数组但它有自己的语言特性和内存特性比如不可变性、结尾标识符、编码问题这些坑如果不在训练营阶段踩一遍后续做工程、刷笔试题的时候会反复掉进去。这一天的训练营主题是字符串专题的第二次课也就是 Part02重点覆盖字符串处理的进阶操作反转、替换、翻转单词、左旋、KMP 匹配以及字符串与其他类型之间的转换判断。相比第一天的入门题目Part02 的题目开始要求你在 O(1) 空间内完成原地修改或者理解前缀表为什么能加速匹配难度明显上了一个台阶。这篇文章的价值在于我会把整个 Part02 的题目类型、解题套路、易错细节全部拆开配合实际代码和踩坑记录帮你建立一套字符串题的通用处理框架。适合的人群很明确正在跟着训练营刷题的同学、准备校招笔试的求职者、以及想系统补一下字符串底层原理的开发者。无论你处于哪个阶段读完之后再回头做这些题会明显感觉到思路清楚了。1.2 字符串题的通用底层模型要真正掌握字符串题目第一步不是刷题而是建立正确的底层模型。我在训练营里反复强调一个观点字符串题目本质上考的只有三件事——指针移动、边界控制、状态记录。指针移动解决的是如何在字符串上遍历、定位、分段的问题边界控制解决的是索引会不会越界、循环什么时候终止的问题状态记录解决的是如何用最少的信息判断前后缀匹配的问题。KMP 算法就是状态记录的极致体现。而你看到的反转字符串、替换空格、翻转单词顺序、左旋字符串全部都可以归结为指针移动和边界控制这两个维度的组合。另一个必须建立的认知是字符串在高级语言里是不可变对象。以 Java 和 Python 为例每次修改字符串都会生成新对象这会带来 O(n) 的额外空间。所以在训练营里我们特别强调如果题目要求 O(1) 空间你就必须把字符串转成字符数组或者用 C 这类原生支持修改的语言直接操作。这也是为什么很多训练营的题解用 C 写因为std::string允许通过下标直接修改字符天然适合做原地操作。用 Python 或 Java 的同学也别慌思路完全一样只是多一步转换而已。2. 核心细节解析与实操要点2.1 反转类题目为什么先整体后局部是万能钥匙Part02 里最经典的一类题目是反转字符串和翻转单词顺序。比如力扣 344 题反转字符串要求原地反转字符数组进阶版是 151 题翻转字符串里的单词要求把每个单词内部顺序保留但单词在句子中的顺序反转。先说 344 题。这道题的解法一句话就能说完双指针从两端向中间移动交换左右指针所指字符。但这里有一个细节值得展开交换的终止条件究竟是 left right 还是 left right。如果数组长度为偶数left right 正好能配对完如果数组长度为奇数中间那个字符不需要交换所以 left right 也刚好。用 left right 会发现中间字符和自己交换了一遍虽然是无效操作但不会出错只是白白浪费时间。我在训练营里一直建议大家统一记住 left right逻辑更干净。到了 151 题情况就不一样了。常规思路是先整体反转整个字符串再逐个单词反转——先让整个句子倒序单词内部的字符顺序也跟着倒了再对每个单词做一次反转把内部顺序纠正回来。这个思路我第一次接触时觉得绕但实际操作三次之后就会发现它非常优雅避免了 split 之后拼接带来的额外空间。举一个具体例子字符串是 the sky is blue。第一步整体反转得到 eulb si yks eht第二步逐个单词反转eulb 反转为 bluesi 反转为 isyks 反转为 skyeht 反转为 the最终结果正是 blue is sky the。整个过程只依赖一个反转函数空间复杂度 O(1)完美符合题目进阶要求。2.2 替换类题目从后往前遍历是核心技巧替换空格是另一道高频题。比如把字符串 We are happy. 中的所有空格替换成 %20。最直观的做法是从前往后遍历遇到空格就插入三个字符但这意味着后续所有字符都要往后移动时间复杂度会退化到 O(n²)。训练营里强调的正确方式是从后往前遍历。具体逻辑是先数出字符串里有多少个空格假设是 count 个那么新字符串的长度就是原长度加上 2 * count每个空格从 1 个字符变成 3 个字符净增 2 个。然后设置两个指针一个指向原字符串末尾一个指向新字符串末尾从后往前复制字符。遇到空格时新指针位置依次填入 0、2、%然后跳过原空格继续往前。为什么要从后往前因为从后往前时每个字符只需要移动一次不会出现重复搬移的情况。你可以类比一下搬家如果你从前往后整理房间新家具会挡住旧家具的去路反而要反复挪从最后一间房开始腾位置顺序就顺了。这个技巧在合并两个有序数组的题目里同样适用属于训练营里必须掌握的通用套路。2.3 KMP 算法前缀表到底在记录什么字符串 Part02 里最硬核的内容一定是 KMP 算法对应力扣 28 题实现 strStr()以及 459 题重复的子字符串。很多同学一听到 KMP 就头皮发麻觉得 next 数组推导复杂本质上是因为没有理解清楚前缀表到底在记录什么。前缀表记录的是当前下标位置之前的子串中最长相等前后缀的长度。举个例子模式串是 aabaaf我们逐个位置求前缀表。下标 0 位置字符 a它之前的子串为空最长相等前后缀长度记为 0。下标 1 位置字符 a之前子串是 aa前缀有 a后缀有 a相等最长长度是 1。下标 2 位置字符 b之前子串是 aab前缀 aa 和后缀 ab 不相等前缀 a 和后缀 b 也不相等所以是 0。这样一路算下去得到 [0, 1, 0, 1, 2, 0]。这个表的价值在于当主串匹配到某个位置失败时不需要像暴力解法那样退回模式串的起始位置重新来过而是根据前缀表直接跳到上一个最长相等前缀的末尾继续匹配。前缀表记录的是模式的自我重复信息用来指导失败后回退的步数。可以这么理解你走路踩空了不必退回起点重新走而是站回最近一个稳定落脚的台阶上再继续。2.4 字符串与其他类型的转换判断从热搜词里可以看到字符串和数字之间的转换判断也是一个高频率的实战需求比如 SQLServer 里字符串转数字、Oracle 里过滤不可转为数字的字符串、Python 里判断字符串是否是数字。这些虽然不全是算法题但训练营里必须补充这些工程场景因为它们直接对应 LeetCode 上的 8 题字符串转换整数 (atoi)以及各种语言内置校验函数的底层实现。以 atoi 为例核心逻辑只有四步跳过前导空格、判断正负号、累加数字部分、处理溢出。其中最容易出问题的是溢出判断——不能等累加完再去检查而要在每次累加前判断会不会越界。具体做法是如果当前结果大于 (INT_MAX - 当前数字) / 10说明再加一位就会溢出直接截断返回边界值。在工程场景里Oracle 的REGEXP_LIKE配合正则判断字符串是否为数字、Python 的str.isdigit()只认阿拉伯数字而isnumeric()还能识别罗马数字和汉字数字这些细节在笔试和面试里经常被问到。训练营里建议大家把字符串到数字、数字到字符串两类转换的手写实现都做一遍变量命名和边界处理才会真正刻进脑子里。3. 实操过程与核心环节实现3.1 环境准备和测试用例设计进入实操之前先说明一下环境。我个人的训练营练习环境推荐使用本地 IDE 在线评测双配合语言选择 C 或 Python 都可以。C 的好处是能直接操作字符数组更贴近底层逻辑Python 的好处是快速验证思路但要注意字符串不可变的问题。我自己平时用 Python 验证思路再用 C 提交 LeetCode两种语言都练一遍面试时切换更从容。测试用例设计是很多同学忽略的环节但恰恰是最能体现功力的地方。以反转字符串里的单词为例除了 the sky is blue 这种常规用例一定要测前后都有空格的输入、单词之间多个空格、整个字符串只有一个单词以及空字符串。这四个边界几乎覆盖了 151 题全部容易翻车的点。我自己做题时有个习惯先写测试用例再写实现代码这样思路会更清晰因为边界条件会倒逼你明确循环终止条件和跳过逻辑。3.2 反转字符串里的单词完整实操我们先写一个最简单的反转区间函数然后基于它实现整个逻辑。以下是 Python 版本的实现注意先把字符串转为列表以模拟原地修改def reverse_range(s, left, right): # 反转字符数组中 [left, right] 闭区间内的字符 while left right: s[left], s[right] s[right], s[left] left 1 right - 1 def reverse_words(s: str) - str: # 去除首尾空格并按单词拆分 words s.strip().split() # 先整体反转单词列表 words.reverse() # 再用单个空格拼接 return .join(words)这里用split()是 Python 的偷懒写法默认会按任意空白符拆分并过滤连续空格代码最简洁。但如果要练习真正的原地算法可以参考下面这份更贴近工程底层的写法手动完成去除多余空格 整体反转 单词反转三步def reverse_words_inplace(s: str) - str: # 第一步手工去除多余空格并转为字符列表 chars [] i 0 n len(s) while i n: # 跳过所有空格 while i n and s[i] : i 1 if i n: break # 收集一个单词 if chars: chars.append( ) while i n and s[i] ! : chars.append(s[i]) i 1 # 第二步整体反转 chars.reverse() # 第三步逐个单词反转 start 0 m len(chars) while start m: end start while end m and chars[end] ! : end 1 reverse_range(chars, start, end - 1) start end 1 return .join(chars)第一次跑这段代码我建议你手动模拟一个带连续空格的输入比如 a good example 。你会发现第一步之后字符数组变成[a, , g, o, o, d, , e, x, a, m, p, l, e]连续空格被压缩成单个首尾空格全部消失。整体反转后再逐个单词反转结果就是 example good a。整个流程每一步都清晰可见这就是手写实现的价值。3.3 KMP 前缀表构建与匹配过程接下来是 KMP 的实现。先构建 next 数组也就是前缀表。这里我采用next 数组整体右移一位首位置为 -1的常见变体方便匹配时统一处理。def get_next(pattern: str): n len(pattern) next_arr [0] * n j 0 # 前缀末尾指针同时代表当前最长相等前后缀长度 for i in range(1, n): # 不相等时j 回退到前一个位置的 next 值 while j 0 and pattern[i] ! pattern[j]: j next_arr[j - 1] # 相等时前缀长度加一 if pattern[i] pattern[j]: j 1 next_arr[i] j return next_arr def kmp_search(text: str, pattern: str) - int: if not pattern: return 0 next_arr get_next(pattern) j 0 for i in range(len(text)): while j 0 and text[i] ! pattern[j]: j next_arr[j - 1] if text[i] pattern[j]: j 1 if j len(pattern): return i - len(pattern) 1 return -1代码里的核心难点在while j 0 and text[i] ! pattern[j]这一行很多同学不理解为什么失败后要回退到next_arr[j - 1]。我的理解方式是j代表的是当前已经匹配了 j 个字符一旦模式串下标 j 与主串不匹配说明前 j 个字符是匹配的。这前 j 个字符的最长相等前后缀长度记录在next_arr[j - 1]里所以直接用这个长度作为新的 j跳过那些不可能匹配的位置。这个过程是整个 KMP 算法效率的根源。3.4 atoi 字符串转整数的边界处理实战手写一个 atoi 是训练营里性价比很高的题目因为它集中考察了溢出、正负号、空白字符三大边界。以下是我推荐的一个 Python 实现def my_atoi(s: str) - int: s s.lstrip() if not s: return 0 sign 1 idx 0 if s[0] in -: if s[0] -: sign -1 idx 1 # 使用长整型避免中间溢出 result 0 INT_MAX 2**31 - 1 INT_MIN -2**31 while idx len(s) and s[idx].isdigit(): digit ord(s[idx]) - ord(0) if result (INT_MAX - digit) // 10: return INT_MAX if sign 1 else INT_MIN result result * 10 digit idx 1 return sign * result注意看溢出判断那一行result (INT_MAX - digit) // 10本质上是把不等式result * 10 digit INT_MAX移项变形避免先乘后加导致溢出。如果你先result result * 10 digit再去判断可能 result 已经炸掉了Python 因为有大整数所以没事但 C 里这是经典的未定义行为。训练营里我要求大家必须用这种先判断再计算的写法养成习惯后在系统设计、金融计费等场景里会少踩很多坑。4. 常见问题与排查技巧实录4.1 反转字符串忘记考虑单词间空格导致结果粘连这是 151 题最常见的错误。很多同学第一次写会直接s[::-1]整体反转字符再按空格 split结果发现单词内部字符顺序也反了拼接后单词里出现倒序比如 blue 变成 eulb。排查方法很简单分步打印中间结果。如果你用了整体反转再局部反转的策略第一步之后打印一下字符串检查一下是不是所有字符顺序确实反了第二步每个单词反转后再核对单词本身是否恢复正确。只要这两步都验证通过结果基本不会错。另外一类错误是输出格式题目要求单词之间用一个空格分隔并且首尾不能有多余空格。如果第一步处理多余空格时逻辑写错输出里会夹带多个空格甚至空单词。建议在去掉多余空格的循环里加一个打印语句观察连续空格是否被正确跳过。4.2 KMP 前缀表求错匹配结果莫名其妙KMP 的 next 数组是最容易出 bug 的地方。一种常见错误是 j 回退条件写成了j 0 and pattern[i] ! pattern[j]但回退语句写成j - 1这是错的——应该回退到next_arr[j - 1]。如果只减一算法退化成一种跳跃式的暴力匹配某些用例能过但复杂用例会超时或者答案错误。排查 next 数组是否正确最常用的方法是拿一个已知的小字符串手算一遍。比如 ababca正确的前缀表应该是 [0, 0, 1, 2, 3, 0]。你可以打印出代码计算的结果逐位对比。如果发现某一位不一致重点检查该位置之前的所有字符尤其是连续相同字符和断层字符的情况。经验法则是只要前缀表用最长相等前后缀的语义去理解回退逻辑就永远不会记混。4.3 字符串转数字时正负号和空格处理顺序搞反atoi 这类题目有个隐晦的坑题目要求先跳过前导空格再判断正负号。如果先判断正负号再跳过空格遇到 -42 这种输入会直接判定正负号不合法而返回 0。正确顺序永远是先lstrip跳过空格再检查第一个非空字符是不是正负号。如果第一个非空字符既不是数字也不是正负号直接返回 0。还有一坑是 C 实现里用int存储中间结果会导致溢出之后符号翻转成负数进而影响判断。建议用long long存储并加阈值判断或者像我前面写的那样在累加前预判。这里补充一个工程小技巧如果你不想手写溢出判断可以先abs(INT_MIN)这种极其危险的操作所以正规实现必须用边界值除以 10 做预判千万不要用更复杂的方式绕。4.4 实战经验补充多用打印中间态而不是纯脑补我踩过的最大坑是总觉得代码逻辑没问题结果一提交就失败。后来养成一个习惯在任何循环、任何反转操作之后打印当前字符串或数组状态。每打印一次相当于给代码拍一张 X 光片。尤其是涉及双指针的题目打印 left 和 right 的值能迅速发现指针移动条件是否错误。比如反转单词那题很多同学会忘记在单词内层循环结束后更新 start 为end 1导致死循环或者单词重复处理。打印 start 和 end 的每一轮取值这个问题一眼就能看出来。这个习惯不只适用于算法题日常处理 JSON 字符串、日志解析、SQL 拼接等工作中同样好用建议尽早养成。4.5 字符串排序与哈希相关容易被忽视的热身题另外从热搜词里看到很多人关注字符串排序和字符串匹配相关题目。这类题目在训练营中虽然不属于主讲内容但我会安排一组热身题比如按字母频率排序字符串、判断两个字符串是否互为变位词。这类题的核心是哈希计数也就是把字符映射到 26 个桶或 128 个 ASCII 码桶里统计每个字符出现次数再按需求输出。别看简单它几乎是所有字符串题目的入门口也是很多复杂题的 pre-step。实操时注意一点计数数组的索引不要直接用字符变量而要先转成相对偏移量。比如count[ord(c) - ord(a)] 1这样数组下标是从 0 到 25避免出现越界。这个细节在 C 里尤其重要因为char类型做数组下标时可能因为符号问题变成负数。训练营里提到的字符串排序题本质上就是计数 按序输出理解了这个逻辑后你再看任何排序需求都会更容易找到突破口。5. 训练营学习方法与周测复盘建议5.1 每天刷题节奏怎么安排才不容易崩字符串 Part02 的题量虽然大但不需要一次性全部写完。我建议的训练节奏是每天 2 道新题 1 道旧题复习每道题限时 25 分钟。如果 25 分钟没有思路立刻看题解但看完题解之后必须关掉题解独立重写一遍直到能一气呵成写出来为止。这个方法比死磕两小时效率高得多因为字符串题目很多套路是见过就会没见过就很难比如先整体反转再局部反转这个技巧第一次想出来确实不容易但看过一次之后就得刻进肌肉记忆。训练营里我还鼓励大家建立自己的错题本记录三要素题目链接、错误代码、错误原因。不要只记正确代码而是要写清楚我为什么错。比如我自己错题本里有一条151 题第二次做的时候忘记处理首尾空格原因是编辑器自动帮我去除了空格但 LeetCode 的测试用例不会。这种记录比任何笔记都更能防止同类错误复发。5.2 周测复盘用双指针技巧串联所有字符串题Part02 结束之后有一个关键动作就是复盘这周学到的双指针技巧。你会发现反转字符串、替换空格、翻转单词、移动元素全部都是双指针在字符串上的变体。一个左指针一个右指针要么相向移动要么同向移动要么一个快一个慢本质都是用指针标记位置避免额外空间。复盘时我建议做一张表把题目和技巧对应起来反转字符串对应相向双指针替换空格对应从后往前的双向指针翻转单词对应先整体后局部的双指针组合KMP 虽然不用双指针但它的 next 数组本质上是一个已匹配长度指针的回退过程。这样横向对比后你就不会觉得每道题都是孤立的而是会看到字符串题背后那套统一的方法论。5.3 关于 go、rust、java 三种语言的实现差异训练营里很多同学会问到不同语言怎么写字符串。这里补充一点我的经验Java 和 Python 的字符串不可变所以 O(1) 空间限制下必须先toCharArray()或list()转成可变序列C 的string可以直接改所以代码最简洁Go 的字符串也是不可变的要转成[]rune或[]byte处理而且注意[]byte按字节处理时遇到中文会乱必须转[]rune。Rust 更特殊字符串按 UTF-8 字节存储直接按索引访问会 panic需要先转成 char 集合。这些差异决定了不同语言下同一道题的实现细节完全不同。如果面试要求你用特定语言务必提前确认该语言的字符串特性和转换 API。训练营里我会建议主流求职方向的同学用 Java 或 Python 作为主语言C 作为副语言理解底层原理Go 或 Rust 作为加分项这样覆盖最全面。6. 下一步进阶方向字符串专题到这里其实只完成了一半。Part02 之后后续训练营会自然地进入栈与队列和二叉树专题。双指针技巧会在链表中继续发挥大作用KMP 的思想会在更复杂的模式匹配问题里延伸比如通配符匹配、正则表达式匹配这些 hard 题它们只不过是在 KMP 的思路上叠加了动态规划的状态设计。如果你想把字符串这块学得更深我个人的进阶建议是先把 LeetCode 上字符串分类下简单和中等难度的题目全部刷一遍尤其是编辑距离、最长公共子序列、最长回文子串这几道经典题它们会强迫你把字符串当作序列去思考而不是停留在简单的字符操作层面。等到动态规划专题开始后你会发现自己对字符串的理解会再上一个台阶。最后再分享一个小技巧。我在刷字符串题时有一个习惯只把每个题的框架、核心技巧和易错边界记在错题本上不看完整代码。下次遇到同类题目时先尝试能否独立推导出核心步骤推导不出来再翻错题本。这样反复训练之后你会明显感觉到从看懂题解到独立写出之间的距离在慢慢缩短而这种感觉比刷题数量更让人安心。 
长河君 · 2026/9/28 15:13:20 · 阅读 1.2k 字符串算法进阶：反转、KMP与atoi的核心套路
1. 内容整体设计与思路拆解1.1 为什么第八天会卡在字符串这道坎上说真的算法训练营走到第九天能坚持下来的同学已经干掉了一批人。前面几天我们啃完了数组、链表、哈希表、双指针这些基础结构到了字符串这一块很多人会误以为字符串不就是字符数组吗有什么好学的。结果一上手做题就懵了——明明思路好像是对的代码写出来却总是越界、反转不到位、拼接顺序反了。这背后的核心原因在于字符串虽然底层是字符数组但它有自己的语言特性和内存特性比如不可变性、结尾标识符、编码问题这些坑如果不在训练营阶段踩一遍后续做工程、刷笔试题的时候会反复掉进去。这一天的训练营主题是字符串专题的第二次课也就是 Part02重点覆盖字符串处理的进阶操作反转、替换、翻转单词、左旋、KMP 匹配以及字符串与其他类型之间的转换判断。相比第一天的入门题目Part02 的题目开始要求你在 O(1) 空间内完成原地修改或者理解前缀表为什么能加速匹配难度明显上了一个台阶。这篇文章的价值在于我会把整个 Part02 的题目类型、解题套路、易错细节全部拆开配合实际代码和踩坑记录帮你建立一套字符串题的通用处理框架。适合的人群很明确正在跟着训练营刷题的同学、准备校招笔试的求职者、以及想系统补一下字符串底层原理的开发者。无论你处于哪个阶段读完之后再回头做这些题会明显感觉到思路清楚了。1.2 字符串题的通用底层模型要真正掌握字符串题目第一步不是刷题而是建立正确的底层模型。我在训练营里反复强调一个观点字符串题目本质上考的只有三件事——指针移动、边界控制、状态记录。指针移动解决的是如何在字符串上遍历、定位、分段的问题边界控制解决的是索引会不会越界、循环什么时候终止的问题状态记录解决的是如何用最少的信息判断前后缀匹配的问题。KMP 算法就是状态记录的极致体现。而你看到的反转字符串、替换空格、翻转单词顺序、左旋字符串全部都可以归结为指针移动和边界控制这两个维度的组合。另一个必须建立的认知是字符串在高级语言里是不可变对象。以 Java 和 Python 为例每次修改字符串都会生成新对象这会带来 O(n) 的额外空间。所以在训练营里我们特别强调如果题目要求 O(1) 空间你就必须把字符串转成字符数组或者用 C 这类原生支持修改的语言直接操作。这也是为什么很多训练营的题解用 C 写因为std::string允许通过下标直接修改字符天然适合做原地操作。用 Python 或 Java 的同学也别慌思路完全一样只是多一步转换而已。2. 核心细节解析与实操要点2.1 反转类题目为什么先整体后局部是万能钥匙Part02 里最经典的一类题目是反转字符串和翻转单词顺序。比如力扣 344 题反转字符串要求原地反转字符数组进阶版是 151 题翻转字符串里的单词要求把每个单词内部顺序保留但单词在句子中的顺序反转。先说 344 题。这道题的解法一句话就能说完双指针从两端向中间移动交换左右指针所指字符。但这里有一个细节值得展开交换的终止条件究竟是 left right 还是 left right。如果数组长度为偶数left right 正好能配对完如果数组长度为奇数中间那个字符不需要交换所以 left right 也刚好。用 left right 会发现中间字符和自己交换了一遍虽然是无效操作但不会出错只是白白浪费时间。我在训练营里一直建议大家统一记住 left right逻辑更干净。到了 151 题情况就不一样了。常规思路是先整体反转整个字符串再逐个单词反转——先让整个句子倒序单词内部的字符顺序也跟着倒了再对每个单词做一次反转把内部顺序纠正回来。这个思路我第一次接触时觉得绕但实际操作三次之后就会发现它非常优雅避免了 split 之后拼接带来的额外空间。举一个具体例子字符串是 the sky is blue。第一步整体反转得到 eulb si yks eht第二步逐个单词反转eulb 反转为 bluesi 反转为 isyks 反转为 skyeht 反转为 the最终结果正是 blue is sky the。整个过程只依赖一个反转函数空间复杂度 O(1)完美符合题目进阶要求。2.2 替换类题目从后往前遍历是核心技巧替换空格是另一道高频题。比如把字符串 We are happy. 中的所有空格替换成 %20。最直观的做法是从前往后遍历遇到空格就插入三个字符但这意味着后续所有字符都要往后移动时间复杂度会退化到 O(n²)。训练营里强调的正确方式是从后往前遍历。具体逻辑是先数出字符串里有多少个空格假设是 count 个那么新字符串的长度就是原长度加上 2 * count每个空格从 1 个字符变成 3 个字符净增 2 个。然后设置两个指针一个指向原字符串末尾一个指向新字符串末尾从后往前复制字符。遇到空格时新指针位置依次填入 0、2、%然后跳过原空格继续往前。为什么要从后往前因为从后往前时每个字符只需要移动一次不会出现重复搬移的情况。你可以类比一下搬家如果你从前往后整理房间新家具会挡住旧家具的去路反而要反复挪从最后一间房开始腾位置顺序就顺了。这个技巧在合并两个有序数组的题目里同样适用属于训练营里必须掌握的通用套路。2.3 KMP 算法前缀表到底在记录什么字符串 Part02 里最硬核的内容一定是 KMP 算法对应力扣 28 题实现 strStr()以及 459 题重复的子字符串。很多同学一听到 KMP 就头皮发麻觉得 next 数组推导复杂本质上是因为没有理解清楚前缀表到底在记录什么。前缀表记录的是当前下标位置之前的子串中最长相等前后缀的长度。举个例子模式串是 aabaaf我们逐个位置求前缀表。下标 0 位置字符 a它之前的子串为空最长相等前后缀长度记为 0。下标 1 位置字符 a之前子串是 aa前缀有 a后缀有 a相等最长长度是 1。下标 2 位置字符 b之前子串是 aab前缀 aa 和后缀 ab 不相等前缀 a 和后缀 b 也不相等所以是 0。这样一路算下去得到 [0, 1, 0, 1, 2, 0]。这个表的价值在于当主串匹配到某个位置失败时不需要像暴力解法那样退回模式串的起始位置重新来过而是根据前缀表直接跳到上一个最长相等前缀的末尾继续匹配。前缀表记录的是模式的自我重复信息用来指导失败后回退的步数。可以这么理解你走路踩空了不必退回起点重新走而是站回最近一个稳定落脚的台阶上再继续。2.4 字符串与其他类型的转换判断从热搜词里可以看到字符串和数字之间的转换判断也是一个高频率的实战需求比如 SQLServer 里字符串转数字、Oracle 里过滤不可转为数字的字符串、Python 里判断字符串是否是数字。这些虽然不全是算法题但训练营里必须补充这些工程场景因为它们直接对应 LeetCode 上的 8 题字符串转换整数 (atoi)以及各种语言内置校验函数的底层实现。以 atoi 为例核心逻辑只有四步跳过前导空格、判断正负号、累加数字部分、处理溢出。其中最容易出问题的是溢出判断——不能等累加完再去检查而要在每次累加前判断会不会越界。具体做法是如果当前结果大于 (INT_MAX - 当前数字) / 10说明再加一位就会溢出直接截断返回边界值。在工程场景里Oracle 的REGEXP_LIKE配合正则判断字符串是否为数字、Python 的str.isdigit()只认阿拉伯数字而isnumeric()还能识别罗马数字和汉字数字这些细节在笔试和面试里经常被问到。训练营里建议大家把字符串到数字、数字到字符串两类转换的手写实现都做一遍变量命名和边界处理才会真正刻进脑子里。3. 实操过程与核心环节实现3.1 环境准备和测试用例设计进入实操之前先说明一下环境。我个人的训练营练习环境推荐使用本地 IDE 在线评测双配合语言选择 C 或 Python 都可以。C 的好处是能直接操作字符数组更贴近底层逻辑Python 的好处是快速验证思路但要注意字符串不可变的问题。我自己平时用 Python 验证思路再用 C 提交 LeetCode两种语言都练一遍面试时切换更从容。测试用例设计是很多同学忽略的环节但恰恰是最能体现功力的地方。以反转字符串里的单词为例除了 the sky is blue 这种常规用例一定要测前后都有空格的输入、单词之间多个空格、整个字符串只有一个单词以及空字符串。这四个边界几乎覆盖了 151 题全部容易翻车的点。我自己做题时有个习惯先写测试用例再写实现代码这样思路会更清晰因为边界条件会倒逼你明确循环终止条件和跳过逻辑。3.2 反转字符串里的单词完整实操我们先写一个最简单的反转区间函数然后基于它实现整个逻辑。以下是 Python 版本的实现注意先把字符串转为列表以模拟原地修改def reverse_range(s, left, right): # 反转字符数组中 [left, right] 闭区间内的字符 while left right: s[left], s[right] s[right], s[left] left 1 right - 1 def reverse_words(s: str) - str: # 去除首尾空格并按单词拆分 words s.strip().split() # 先整体反转单词列表 words.reverse() # 再用单个空格拼接 return .join(words)这里用split()是 Python 的偷懒写法默认会按任意空白符拆分并过滤连续空格代码最简洁。但如果要练习真正的原地算法可以参考下面这份更贴近工程底层的写法手动完成去除多余空格 整体反转 单词反转三步def reverse_words_inplace(s: str) - str: # 第一步手工去除多余空格并转为字符列表 chars [] i 0 n len(s) while i n: # 跳过所有空格 while i n and s[i] : i 1 if i n: break # 收集一个单词 if chars: chars.append( ) while i n and s[i] ! : chars.append(s[i]) i 1 # 第二步整体反转 chars.reverse() # 第三步逐个单词反转 start 0 m len(chars) while start m: end start while end m and chars[end] ! : end 1 reverse_range(chars, start, end - 1) start end 1 return .join(chars)第一次跑这段代码我建议你手动模拟一个带连续空格的输入比如 a good example 。你会发现第一步之后字符数组变成[a, , g, o, o, d, , e, x, a, m, p, l, e]连续空格被压缩成单个首尾空格全部消失。整体反转后再逐个单词反转结果就是 example good a。整个流程每一步都清晰可见这就是手写实现的价值。3.3 KMP 前缀表构建与匹配过程接下来是 KMP 的实现。先构建 next 数组也就是前缀表。这里我采用next 数组整体右移一位首位置为 -1的常见变体方便匹配时统一处理。def get_next(pattern: str): n len(pattern) next_arr [0] * n j 0 # 前缀末尾指针同时代表当前最长相等前后缀长度 for i in range(1, n): # 不相等时j 回退到前一个位置的 next 值 while j 0 and pattern[i] ! pattern[j]: j next_arr[j - 1] # 相等时前缀长度加一 if pattern[i] pattern[j]: j 1 next_arr[i] j return next_arr def kmp_search(text: str, pattern: str) - int: if not pattern: return 0 next_arr get_next(pattern) j 0 for i in range(len(text)): while j 0 and text[i] ! pattern[j]: j next_arr[j - 1] if text[i] pattern[j]: j 1 if j len(pattern): return i - len(pattern) 1 return -1代码里的核心难点在while j 0 and text[i] ! pattern[j]这一行很多同学不理解为什么失败后要回退到next_arr[j - 1]。我的理解方式是j代表的是当前已经匹配了 j 个字符一旦模式串下标 j 与主串不匹配说明前 j 个字符是匹配的。这前 j 个字符的最长相等前后缀长度记录在next_arr[j - 1]里所以直接用这个长度作为新的 j跳过那些不可能匹配的位置。这个过程是整个 KMP 算法效率的根源。3.4 atoi 字符串转整数的边界处理实战手写一个 atoi 是训练营里性价比很高的题目因为它集中考察了溢出、正负号、空白字符三大边界。以下是我推荐的一个 Python 实现def my_atoi(s: str) - int: s s.lstrip() if not s: return 0 sign 1 idx 0 if s[0] in -: if s[0] -: sign -1 idx 1 # 使用长整型避免中间溢出 result 0 INT_MAX 2**31 - 1 INT_MIN -2**31 while idx len(s) and s[idx].isdigit(): digit ord(s[idx]) - ord(0) if result (INT_MAX - digit) // 10: return INT_MAX if sign 1 else INT_MIN result result * 10 digit idx 1 return sign * result注意看溢出判断那一行result (INT_MAX - digit) // 10本质上是把不等式result * 10 digit INT_MAX移项变形避免先乘后加导致溢出。如果你先result result * 10 digit再去判断可能 result 已经炸掉了Python 因为有大整数所以没事但 C 里这是经典的未定义行为。训练营里我要求大家必须用这种先判断再计算的写法养成习惯后在系统设计、金融计费等场景里会少踩很多坑。4. 常见问题与排查技巧实录4.1 反转字符串忘记考虑单词间空格导致结果粘连这是 151 题最常见的错误。很多同学第一次写会直接s[::-1]整体反转字符再按空格 split结果发现单词内部字符顺序也反了拼接后单词里出现倒序比如 blue 变成 eulb。排查方法很简单分步打印中间结果。如果你用了整体反转再局部反转的策略第一步之后打印一下字符串检查一下是不是所有字符顺序确实反了第二步每个单词反转后再核对单词本身是否恢复正确。只要这两步都验证通过结果基本不会错。另外一类错误是输出格式题目要求单词之间用一个空格分隔并且首尾不能有多余空格。如果第一步处理多余空格时逻辑写错输出里会夹带多个空格甚至空单词。建议在去掉多余空格的循环里加一个打印语句观察连续空格是否被正确跳过。4.2 KMP 前缀表求错匹配结果莫名其妙KMP 的 next 数组是最容易出 bug 的地方。一种常见错误是 j 回退条件写成了j 0 and pattern[i] ! pattern[j]但回退语句写成j - 1这是错的——应该回退到next_arr[j - 1]。如果只减一算法退化成一种跳跃式的暴力匹配某些用例能过但复杂用例会超时或者答案错误。排查 next 数组是否正确最常用的方法是拿一个已知的小字符串手算一遍。比如 ababca正确的前缀表应该是 [0, 0, 1, 2, 3, 0]。你可以打印出代码计算的结果逐位对比。如果发现某一位不一致重点检查该位置之前的所有字符尤其是连续相同字符和断层字符的情况。经验法则是只要前缀表用最长相等前后缀的语义去理解回退逻辑就永远不会记混。4.3 字符串转数字时正负号和空格处理顺序搞反atoi 这类题目有个隐晦的坑题目要求先跳过前导空格再判断正负号。如果先判断正负号再跳过空格遇到 -42 这种输入会直接判定正负号不合法而返回 0。正确顺序永远是先lstrip跳过空格再检查第一个非空字符是不是正负号。如果第一个非空字符既不是数字也不是正负号直接返回 0。还有一坑是 C 实现里用int存储中间结果会导致溢出之后符号翻转成负数进而影响判断。建议用long long存储并加阈值判断或者像我前面写的那样在累加前预判。这里补充一个工程小技巧如果你不想手写溢出判断可以先abs(INT_MIN)这种极其危险的操作所以正规实现必须用边界值除以 10 做预判千万不要用更复杂的方式绕。4.4 实战经验补充多用打印中间态而不是纯脑补我踩过的最大坑是总觉得代码逻辑没问题结果一提交就失败。后来养成一个习惯在任何循环、任何反转操作之后打印当前字符串或数组状态。每打印一次相当于给代码拍一张 X 光片。尤其是涉及双指针的题目打印 left 和 right 的值能迅速发现指针移动条件是否错误。比如反转单词那题很多同学会忘记在单词内层循环结束后更新 start 为end 1导致死循环或者单词重复处理。打印 start 和 end 的每一轮取值这个问题一眼就能看出来。这个习惯不只适用于算法题日常处理 JSON 字符串、日志解析、SQL 拼接等工作中同样好用建议尽早养成。4.5 字符串排序与哈希相关容易被忽视的热身题另外从热搜词里看到很多人关注字符串排序和字符串匹配相关题目。这类题目在训练营中虽然不属于主讲内容但我会安排一组热身题比如按字母频率排序字符串、判断两个字符串是否互为变位词。这类题的核心是哈希计数也就是把字符映射到 26 个桶或 128 个 ASCII 码桶里统计每个字符出现次数再按需求输出。别看简单它几乎是所有字符串题目的入门口也是很多复杂题的 pre-step。实操时注意一点计数数组的索引不要直接用字符变量而要先转成相对偏移量。比如count[ord(c) - ord(a)] 1这样数组下标是从 0 到 25避免出现越界。这个细节在 C 里尤其重要因为char类型做数组下标时可能因为符号问题变成负数。训练营里提到的字符串排序题本质上就是计数 按序输出理解了这个逻辑后你再看任何排序需求都会更容易找到突破口。5. 训练营学习方法与周测复盘建议5.1 每天刷题节奏怎么安排才不容易崩字符串 Part02 的题量虽然大但不需要一次性全部写完。我建议的训练节奏是每天 2 道新题 1 道旧题复习每道题限时 25 分钟。如果 25 分钟没有思路立刻看题解但看完题解之后必须关掉题解独立重写一遍直到能一气呵成写出来为止。这个方法比死磕两小时效率高得多因为字符串题目很多套路是见过就会没见过就很难比如先整体反转再局部反转这个技巧第一次想出来确实不容易但看过一次之后就得刻进肌肉记忆。训练营里我还鼓励大家建立自己的错题本记录三要素题目链接、错误代码、错误原因。不要只记正确代码而是要写清楚我为什么错。比如我自己错题本里有一条151 题第二次做的时候忘记处理首尾空格原因是编辑器自动帮我去除了空格但 LeetCode 的测试用例不会。这种记录比任何笔记都更能防止同类错误复发。5.2 周测复盘用双指针技巧串联所有字符串题Part02 结束之后有一个关键动作就是复盘这周学到的双指针技巧。你会发现反转字符串、替换空格、翻转单词、移动元素全部都是双指针在字符串上的变体。一个左指针一个右指针要么相向移动要么同向移动要么一个快一个慢本质都是用指针标记位置避免额外空间。复盘时我建议做一张表把题目和技巧对应起来反转字符串对应相向双指针替换空格对应从后往前的双向指针翻转单词对应先整体后局部的双指针组合KMP 虽然不用双指针但它的 next 数组本质上是一个已匹配长度指针的回退过程。这样横向对比后你就不会觉得每道题都是孤立的而是会看到字符串题背后那套统一的方法论。5.3 关于 go、rust、java 三种语言的实现差异训练营里很多同学会问到不同语言怎么写字符串。这里补充一点我的经验Java 和 Python 的字符串不可变所以 O(1) 空间限制下必须先toCharArray()或list()转成可变序列C 的string可以直接改所以代码最简洁Go 的字符串也是不可变的要转成[]rune或[]byte处理而且注意[]byte按字节处理时遇到中文会乱必须转[]rune。Rust 更特殊字符串按 UTF-8 字节存储直接按索引访问会 panic需要先转成 char 集合。这些差异决定了不同语言下同一道题的实现细节完全不同。如果面试要求你用特定语言务必提前确认该语言的字符串特性和转换 API。训练营里我会建议主流求职方向的同学用 Java 或 Python 作为主语言C 作为副语言理解底层原理Go 或 Rust 作为加分项这样覆盖最全面。6. 下一步进阶方向字符串专题到这里其实只完成了一半。Part02 之后后续训练营会自然地进入栈与队列和二叉树专题。双指针技巧会在链表中继续发挥大作用KMP 的思想会在更复杂的模式匹配问题里延伸比如通配符匹配、正则表达式匹配这些 hard 题它们只不过是在 KMP 的思路上叠加了动态规划的状态设计。如果你想把字符串这块学得更深我个人的进阶建议是先把 LeetCode 上字符串分类下简单和中等难度的题目全部刷一遍尤其是编辑距离、最长公共子序列、最长回文子串这几道经典题它们会强迫你把字符串当作序列去思考而不是停留在简单的字符操作层面。等到动态规划专题开始后你会发现自己对字符串的理解会再上一个台阶。最后再分享一个小技巧。我在刷字符串题时有一个习惯只把每个题的框架、核心技巧和易错边界记在错题本上不看完整代码。下次遇到同类题目时先尝试能否独立推导出核心步骤推导不出来再翻错题本。这样反复训练之后你会明显感觉到从看懂题解到独立写出之间的距离在慢慢缩短而这种感觉比刷题数量更让人安心。