反转字符串中的单词这道题,几乎是所有刷力扣的人都会遇到的一道“入门级中等题”。说是中等,其实难点不在算法本身,而在你对字符串操作的熟练度、对边界条件的敏感度,以及能否在设计解法时跳出“从头到尾处理”的惯性思维。我刷这道题的时候就有一种很强烈的感受:它考察的不是你会不会反转,而是你会不会用双指针、会不会逆向思考、能不能把字符串的内存布局在脑子里画出来。今天我把这道题从题目拆解、解题思路到代码实现、常见踩坑,完整地梳理一遍,希望能帮到正在刷力扣热题100、准备面试算法轮的朋友。
先说结论:这道题最优雅、最考察功力的解法,是使用“整体反转 + 单词反转”的两步走策略,在空间复杂度上做到 O(1)。当然,如果你是在快速笔试环境里解决问题,Python 的一行 split 解法也足够应付大多数场景。两种思路我都会讲,还会把每一步背后的“为什么”讲透,毕竟面试官真正想听的,从来不只是答案。
1. 内容整体设计与思路拆解
1.1 这道题到底在考什么
先来看看题目的要求:给定一个字符串,逐个反转字符串中的每个单词,同时要注意几点——单词之间可能包含多个空格,字符串首尾可能有空格,反转后的单词之间要保留一个空格,且首尾不能有空格。
很多人第一次看到题目会觉得很简单:先按空格切分,剔除空字符串,反转列表,再拼接回去。确实,这是最直观的思路,很多语言的函数库都能轻松实现。但如果你只停留在这一步,那这道题真正想考察的东西就被你错过了。
这道题的核心考点有三个:第一,如何处理连续空格;第二,能否在 O(1) 额外空间内完成任务;第三,边界条件的敏感度。尤其是在 C++、Java 这类语言里,字符串是不可变的,要做到原地操作就需要把字符串转成字符数组,每一步的索引计算都要特别小心。面试里这道题如果作为热身题出现,面试官通常会追问“能不能不用 split 库函数,自己实现一遍”,这时候如果你能稳稳给出原地解法,观感会完全不一样。
1.2 两种主流思路的对比与选择
我先把这道题的两种主流解法摆出来对比着看,这样你能更清楚地理解为什么下一步要选哪条路。
| 方案 | 核心思路 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 方案一:调用库函数 | 按空格 split,过滤空串,reverse,join | O(n) | O(n) 存储单词列表 | 日常业务代码、快速 AC |
| 方案二:整体反转 + 局部反转 | 先反转整个字符串,再逐个反转每个单词 | O(n) | O(1)(原地操作) | 面试手写、内存受限、考察功底 |
方案一胜在简洁,但它绕过了这道题真正想训练的能力:手写字符串处理逻辑。方案二则要求你理解一个非常经典的技巧——两次反转互相抵消。这背后的逻辑其实可以类比生活中的场景:你想把一排积木按反序排列,一种办法是直接搬动每一块,另一种办法是把整排积木倒过来,再把每个积木内部的正反面也倒回来。后者看似多了一步,但每一步都非常机械、非常高效。
我在实际刷题时会先写方案一快速 AC,确认思路正确后再用方案二实现一遍,刻意训练自己的原地操作能力。这个习惯我推荐给所有准备面试的读者,因为面试考的就是你能不能脱离库函数独立解决。
2. 核心细节解析与实操要点
2.1 整体反转 + 局部反转的内层逻辑
我们先来手推一遍这个流程,加深理解。假设输入字符串是"hello world from python",注意这里有两个连续空格和首尾空格,是我们故意构造的麻烦场景。
第一步,整体反转。反转后变成"nohtyp morf dlrow olleh"。
第二步,局部反转每个单词。扫描过程中,把"nohtyp"反转为"python",把"morf"反转为"from",把"dlrow"反转为"world",把"olleh"反转为"hello"。结果就是"python from world hello"。
你发现关键点了吗?整体反转把单词顺序颠倒了,但每个单词内部的字母也一并颠倒了;局部反转再把每个单词的字母颠倒回来,单词顺序就恢复了。这两个操作叠加,正好还原了每个单词内部的字母顺序,同时完成了单词间的逆序排列。这就是“两次反转互相抵消”的精髓所在。
这里需要特别注意的是第二步的实现方式:我们需要在扫描字符串的过程中,识别出每个单词的起始和结束位置,然后对这个区间内的所有字符进行反转。识别的标准就是空格。换句话说,我们要跳过连续空格,找到单词的左边界,然后继续扫描到空格或字符串末尾,确定右边界,再调用一个反转函数处理这个区间。
2.2 边界条件:最容易翻车的三个地方
这道题有一个特点,就是边界条件特别多,任何一个没处理好,测试用例就会毫不客气地给你亮红灯。我总结了三个最容易翻车的地方。
第一个,字符串首尾有空格。例如" hello world "。如果直接在原始字符串上进行“按空格切分再拼接”的操作,首尾的空格会生成空字符串,导致拼接结果出现多余空格。解决思路是在处理前先清除首尾空格,或者在遍历时跳过空白字符。
第二个,单词之间有多个连续空格。例如"hello world python"。处理这种输入时,按单个空格切分绝对不行,必须采用“跳过所有空格直到非空格字符”的策略。
第三个,字符串本身是空的或全为空格。输入""或" "时,输出应该也是空字符串。很多人在实现原地算法时没有考虑这种极端情况,结果在第一步整体反转时就访问了不存在的索引,直接数组越界。
我把这些边界条件整理成一个自查清单,你在写完代码后可以对照检查:
- 输入为空字符串,返回空字符串
- 输入全部为空格,返回空字符串
- 输入只有一个单词,返回原单词,首尾无空格
- 输入首尾有空格,结果的首尾没有空格
- 输入中间有多个连续空格,结果中间只有一个空格
每次写完这道题,我建议你把这些用例全部手跑一遍,而不是直接依赖测评系统。面试的时候你不可能有即时反馈,这时候心里这张“边界条件检查表”就是你最好的调试工具。
2.3 为什么要强调空间复杂度
很多读者可能会问:既然 split 方案一行就能搞定,为什么还要大费周章地搞什么原地反转?这就要说到面试场景的特殊性了。
面试官想考察的是工程实现能力,而不仅仅是你能不能把题目做出来。使用 split 方案,本质上是在调库,跟面试官想看的“你对字符数组和索引的掌握程度”并不是同一个维度。更进一步说,很多公司还会追问:如果这个字符串长到内存无法完全放下怎么办?此时 O(n) 的辅助空间会变成可怕的负担,而 O(1) 的原地操作仍然可行。用生活类比来解释就是:你要把一列火车从 A 站开到 B 站,方案一是造一条新的铁轨让火车倒着开过去,方案二是原地把火车掉头,顺着原路开回去。前者当然更简单,但后者不需要新铁轨,工程量截然不同。
当然,这并不是说方案一没有价值。在真实的业务写代码中,我反而推荐你用方案一,因为它可读性高、维护成本低。所谓“调用库函数是可耻的”这种言论,平时写业务的时候大可不必理会。刷题练的是功底,写代码讲的是效率,两者不必混为一谈。
3. 实操过程与核心环节实现
3.1 手写一个干净的字符反转函数
要完成整体反转和局部反转,我们需要先实现一个支持区间反转的辅助函数。这个函数是整道题的基石,我建议你把它单独拎出来写,方便复用。
def reverse_range(s, left, right): """反转字符列表 s 中 [left, right] 区间内的字符,原地操作""" while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1这段代码的逻辑非常直观:双指针从区间两端向中间移动,交换对应位置的字符。之所以要 left < right 作为循环条件,是为了保证当区间长度为奇数时,正中间那个字符不需要和自己交换;当区间长度为偶数时,左右指针会在越过彼此后正确结束循环。
这个函数本身很基础,但它有两个细节值得注意。第一,传入的 s 必须是可变对象,Python 字符串是不可变的,所以我们在主函数里要先执行list(s)把字符串转成字符列表。第二,right 参数是闭区间,也就是说如果单词区间是 [start, end],调用时应该传reverse_range(s, start, end),而不是end - 1。这个细节如果记错,会导致每个单词的第一个或最后一个字符没有被反转。
在 C++ 里实现同样的功能就简单一些,因为std::reverse本身就支持区间反转,但那是封闭区间 [first, last),和 Python 的写法略有不同。无论如何,我建议你在刷题时手动写这个函数,而不是依赖标准库,这样对双指针的边界感会更强。
3.2 原地解法的完整实现与逐步解析
下面是这道题原地解法的完整 Python 实现,我逐行做过注释,你要跟着我的思路走一遍,不要只看代码就跳过。
def reverseWords(s: str) -> str: # 第一步:字符串转字符列表,方便原地修改 chars = list(s) n = len(chars) # 第二步:整体反转整个字符列表 reverse_range(chars, 0, n - 1) # 第三步:逐个反转每个单词,并清除多余空格 i = 0 write_index = 0 # 这个指针负责把清理后的字符逐个写回列表前部 while i < n: if chars[i] == ' ': i += 1 continue # 此时 i 指向一个单词的起始位置 if write_index > 0: chars[write_index] = ' ' write_index += 1 # 记录单词起点,用于局部反转 word_start = write_index while i < n and chars[i] != ' ': chars[write_index] = chars[i] write_index += 1 i += 1 # 局部反转当前单词(注意区间是 [word_start, write_index - 1]) reverse_range(chars, word_start, write_index - 1) # 第四步:只保留前 write_index 个字符,因为后面的字符是遗留的旧内容 return ''.join(chars[:write_index])这段代码我第一次看的时候也觉得有点绕,特别是write_index这个指针的作用。我拆开来讲。
整体反转后,整个字符列表顺序颠倒,接着i从原字符串的开头向后扫描,write_index则指向“写回位置”。当i遇到非空格字符,说明进入了一个单词,我们把这个单词的字符逐个往前搬,搬到write_index指向的位置。这样一来,原本分散在字符串后的内容就被组织到了字符串前部,同时跳过了所有连续空格。每搬完一个单词,就用reverse_range把搬过去的那段字符顺序反转回来,得到正确的单词内容。
3.3 为什么需要一个 write_index 指针
这是整道题里最不容易理解的设计。我换个角度说明。
假设经过整体反转后,列表内容是['n', 'o', 'h', 't', 'y', 'p', ' ', ' ', 'd', 'l', 'r', 'o', 'w']。注意这里有两个连续空格。我们期望最终结果是['p', 'y', 't', 'h', 'o', 'n', ' ', 'w', 'o', 'r', 'l', 'd']。
问题来了:原列表里中间有两个空格,但最终结果只需要一个空格。原地操作时,如果直接把字符往原位置写,就会覆盖掉尚未处理的内容。比如当i指向第一个d时,如果我们直接把它写到chars[0]的位置,那么原来的n就被覆盖了,但后面n还没被处理呢。
write_index就是为了解决这个问题而存在的。它始终指向“下一个空闲的写入位置”,只向前移动,不回头。i是读取指针,负责找待处理的字符;write_index是写入指针,负责确定这些字符应该放到哪里。只要write_index <= i始终成立,我们写入的位置要么是已经处理过的区域,要么就是当前正在读取的位置,永远安全。这是典型的“双指针原地压缩”技巧,跟数组去重、移除元素这类题的思路是一脉相通的。
这里有一个容易忽略的点:处理完所有单词后,chars[:write_index]之前的区域才是有效数据,write_index之后的区域还残留着旧内容,必须通过切片丢弃。很多人在这一步忘了截断,或者write_index计算有误导致多余的空格出现在结果里,这些都是我在实际调试中反复遇到过的坑。
3.4 Python 一行流解法的补充说明
如果你只是想快速解题,或者在笔试里时间紧迫,Python 的简洁写法非常值得拥有:
def reverseWords(s: str) -> str: return ' '.join(s.split()[::-1])这两行代码的逻辑是:s.split()默认以任意空白字符(空格、制表符、换行)为分隔符,把字符串拆成单词列表,并且自动忽略空字符串;[::-1]把列表反转;' '.join(...)用单个空格把单词重新拼起来。整个过程不仅是 AC 利器,可读性也极好。
但我必须提醒你,这种写法在工作环境中很合适,在面试手写环节里却可能被视为“回避考点”。面试官追问一句“如果不能用 split 呢”,你就需要回到前面说的原地解法。所以我建议你把两种方法都练熟,形成转换能力。用一个不夸张的比喻来形容这两种方案的差别:一行流解法是坐上高铁,原地解法是学会造铁轨跑完马拉松,前者的成绩单很漂亮,后者才是真正属于你的能力。
4. 常见问题与排查技巧实录
4.1 高频报错与解决方案速查表
这道题是我刷力扣时反复提交次数较多的一题,不是因为想不出思路,而是每次都会被不同的边界条件绊倒。我把遇到过的典型报错和排查思路整理成了表格,方便你对号入座。
| 报错或错误现象 | 典型原因 | 排查方向 |
|---|---|---|
| 报错 String index out of range | 索引访问越界,多半是空字符串或全空格输入直接走了反转逻辑 | 第一步先判断 n 是否为 0 |
| 结果的单词顺序正确但单词内字母顺序错乱 | 局部反转区间边界有误 | 检查 word_start 和 write_index - 1 的关系 |
| 首尾仍有空格 | 没有单独处理首尾空格,或写回时在首位也添加了空格分割符 | 在 write_index > 0 时才插入空格 |
| 单词间保留了多个空格 | 扫描时只跳过了单个空格,没有在 while 里连续跳过 | 用 while i < n and chars[i] == ' ' 连续跳过 |
| 结果尾部出现乱码或旧字符残留 | 没有截断 chars[:write_index] | 返回前确认 join 的区间是有效写入区域 |
| 直接对字符串做索引赋值 | Python 字符串不可变,chars[i] = 'x' 会报 TypeError | 先转 list,处理完 join 回来 |
我自己最常犯的错误,是“在单词间添加空格时没有判断 write_index 是否为 0”。当时我用了一个很刁钻的测试用例"hello"——只有一个单词,结果代码在单词前面多拼了一个空格,输出变成" hello",直接判错。后来我在代码里加上if write_index > 0的判断,这个问题才彻底解决。
4.2 现场调试的一个真实案例
我拿实际跑过的一个用例来演示排查过程。输入为" Alice Bob ",期望输出为"Bob Alice"。
用原地解法处理时,整体反转后变成" boB ecilA "。然后开始扫描,第一次遇到非空格字符是第一个b,于是write_index从 0 开始搬字符,搬完"boB"后局部反转得到"Bob"。接着扫描跳过空格,遇到e,此时write_index指向 4,前面已经有内容"Bob",于是在chars[4]写入一个空格,再开始搬"ecilA",局部反转得到"Alice"。最后write_index指向 10,返回chars[:10],截断后得到"Bob Alice"。
这个过程中我发现一个值得注意的点:由于输入字符串中有连续空格,整体反转后连续空格的位置也会跑回字符串前部,如果你没有write_index这个指针专门负责控制写入位置,就很容易把那些空格也一并保留下来。许多初学者会在这一步直接对整体反转后的字符串做“按空格分割”,结果又绕回了 split 的老路。
4.3 相关题型的进阶串联
力扣热题 100 里,和这道题思路相近的题目其实不少,刷题时最好把它们放在一起对比训练,一鱼多吃。
- 344. 反转字符串:纯双指针反转整个字符数组,是本题的基础拼图。
- 541. 反转字符串 II:在反转的基础上加入区间控制,跟本题的局部反转思路完全一致。
- 557. 反转字符串中的单词 III:这道题是 151 的简化版,只要求反转每个单词内的字符,不要求调整单词顺序。做熟了 151 再回来看它,几乎是秒杀。
- 189. 轮转数组:同样是整体反转 + 局部反转的思路,右移 k 次等价于先反转整体,再反转前 k 个、反转后 n-k 个。
通过这几道题串起来,你会发现“反转”类操作本质上是一个套路:你想调整某一段元素的相对顺序,可以先做一个整体的逆序,再做局部逆序,两次逆序叠加就能实现精准的位移或重排。验证了一个道理想通了,整个系列都顺了。
5. 写在最后的实操心得
每次刷完这道题,我的体会都是同一个:真正有区分度的不是你会不会调用 API,而是你能不能在不依赖 API 的情况下,用一双指针把字符串安排的明明白白。这道题里那个write_index设计,放在真实的文本处理、日志清洗、协议解析这些场景里都有直接的应用价值。比如你在做大数据清洗时,要从一段混杂多个分隔符的文本里提取有效字段,它就是删掉多余分隔符并重排字段位置的天然模型。所以别看它只是力扣的一道题,背后的思想在工程上是能直接迁移的。
最后再分享一个小技巧:刷这类原地操作的字符串题,先在纸上画一次完整的字符数组变化过程,标出每一步i和write_index的位置,不要直接在编辑器里打草稿。画过一轮之后,边界条件就长在脑子里了,写代码的速度至少快一倍,正确率也高得多。