★ FEATURED ARTICLE 拿到这道题的时候我正在整理以前做过的笔试题扫到“反转字符串中单词的字符顺序”这行字一下就想起自己最早写这个逻辑时的混乱状态用两个指针来回摆弄字符串要么把空格一起翻了要么把一个单词拦腰截断要么连续空格直接让程序崩溃。后来把这题彻底吃透才发现它考察的东西远比表面看起来多——字符串边界处理、原地修改的思维、STL对reverse的封装以及不同实现方式在工程场景里的取舍。这篇文章就把这道经典例题掰开揉碎讲清楚。核心目标很明确给定一个字符串字符串里可能有多个单词单词之间用空格隔开现在只反转每个单词内部的字符顺序单词与单词之间的相对位置保持不变。比如I love you经过转换后应该是I evol uoy而不是you love I。适合正在准备笔试面试的开发者、刚学完STL想找综合练习的C初学者也包括工作中偶尔需要处理文本格式的工程师读完这篇你至少能掌握两种完全不同的实现思路并且知道它们各自适合什么场景。1. 把题目嚼碎目标拆解与边界定义1.1 题意的三种常见理解一开始就别跑偏“反转字符串中单词的字符顺序”这句中文描述放在不同语境下可能有三种意思我见得最多的是这三种第一种是最容易和它混淆的反转整个字符串中单词的排列顺序。也就是I love you变成you love I。这个操作在英文题里叫 Reverse Words in a String很多题解用的方法是“先整体反转再逐个单词局部反转”属于另一个经典套路稍后我会专门讲清楚它和本题的核心区别。第二种是对每个单词内部的字符做反转单词之间相对顺序保持不变。I love you变成I evol uoy。这正是标题里“单词的字符顺序”最精确的解释。字符顺序这四个字强调的就是单词内部的字符排列而不是单词排列。第三种是把整个字符串的所有字符直接倒序。I love you变成uoy evol I。如果只是这么干直接调用一次std::reverse就结束了不会成为一道面试题。从标题的措辞来看这道题考察的是第二种情况。接下来的所有实现都围绕它展开。1.2 输入输出约定与边界条件在写代码之前先把题目约定明确掉不然很容易写出“看着对但一测就挂”的版本。输入是一个C标准库中的std::string单词由连续的字母或任意非空格字符组成单词之间以空格分隔。输出是对原字符串做“原地”或“生成新字符串”的处理。这里最折磨人的不是正常情况而是各种边界条件我把实际测试中一定要覆盖的场景列出来空字符串处理完还是空串。只有一个单词没有空格hello反转后是olleh。单词之间有多个连续空格I love you中间是多个空格反转后空格数量应保持不变结果应该是I evol uoy。开头或结尾有空格 hello 结果是 olleh 。单词只有一个字符a b c结果不变翻转一个字符还是它自己。标点符号和数字hello, world123非空格字符当作单词的一部分结果,olleh 321dlrow。这些边界条件在笔试里就是区分“会写”和“写得好”的分水岭。你去看很多公开题解能正确保留连续空格的版本并不多。1.3 为什么说这是一道考察工程细节的好题很多初学者会觉得这题简单遍历字符串遇到空格就把前面那段反转不就行了吗确实主流程就这么朴素。但它的价值恰恰体现在主流程之外的细节上。第一它考察你如何定位“一个单词”的区间。是i和j两个指针同时工作还是先用哨兵变量记录起点这决定了代码的清晰度。第二它考察对std::string底层机制的理解。std::reverse接受迭代器区间必须保证区间合法否则越界就崩。而字符串在最后一位之后还有一个\0这里最容易犯的错是把结尾的空字符也当成可操作对象。第三它考察“是否真的理解原地修改与复制语义的权衡”。如果你在原字符串上直接改空间复杂度是 O(1)但你必须小心翼翼地维护指针如果你新建一个字符串逻辑会简单很多但要额外分配内存还需考虑字符串拼接的性能损失。2. 方法一双指针扫描加原地局部反转2.1 核心思路单词边界就是反转区间先说方法一的思路非常直白。我们维护一个用于扫描的指针让它从左往右走。当它碰到一个非空格字符说明一个单词开始了我们把当前位置记为start。然后继续往前走直到走到字符串结尾或者碰到空格这时当前位置的前一个位置就是单词的结尾记为end。得到的[start, end)区间就是当前这个单词的字符范围直接对这个区间调用std::reverse一次反转搞定。这个思路的关键是反转的粒度是单词不是整个字符串。所以问题的核心变成了“如何准确切出单词区间”。2.2 代码实现与逐步走读先看完整代码#include iostream #include string #include algorithm void reverseWordsInPlace(std::string s) { int n s.size(); int i 0; while (i n) { // 跳过单词之间的空格 if (s[i] ) { i; continue; } // 找到当前单词的起始位置 int start i; // 继续前进到空格或字符串结尾找到单词的结束位置开区间终点 while (i n s[i] ! ) { i; } // 反转整个单词的字符区间 [start, i) std::reverse(s.begin() start, s.begin() i); } } int main() { std::string test I love you; std::cout 转换前: test std::endl; reverseWordsInPlace(test); std::cout 转换后: test std::endl; return 0; }逐行拆一遍int i 0;是总扫描指针。外层while循环判断i n防止越界。if (s[i] )分支处理空格i跳过。这里有个容易被忽略的细节连续空格时每次循环只能跳过一个空格外层循环会反复进入这个分支直到遇到第一个非空格字符为止。这样写的好处是不用另外做“跳过所有空格”的预处理逻辑更统一。遇到非空格字符后start i记录单词起点。内层while继续走条件里i n必须写在前面利用短路求值先判断是否越界再判断字符是否为空格。顺序写反的人我真的见过太多次一旦i已经等于n而你还是先取s[i]那就是读到了越界内存行为和结果都是未知数。std::reverse接收两个迭代器注意它是左闭右开区间反转范围是[start, i)正好就是我们从start到空格之前的所有字符。第一次循环处理完I后i停留在空格位置接着外层判断s[i] 又把它跳过去再进入下一个单词love的处理依次类推。这个版本的核心优点就是额外空间复杂度为 O(1)整个操作都在原字符串上完成结构清晰不容易有多余拷贝。2.3 手工推演让循环过程一目了然光看代码不够我手动走一遍I love you整个过程保证零基础也能明白。初始状态s I love youn 10i 0。第一轮外层循环i 0s[0] 是I不是空格。start 0。内层循环i 从 0 开始s[i] ! ii 1 时s[1] 是空格内层退出。此时区间是[0, 1)只包含字符I。反转单个字符没有变化s 依然是I love you。第二轮外层循环i 1s[1] 是空格进入跳过分支i 2。i 2s[2] 是l不是空格。start 2。内层循环i 2s[2] lii 3s[3] oii 4s[4] vii 5s[5] eii 6s[6] 退出。区间[2, 6)对应love调用std::reverse后变成evol。现在的 s 是I evol you。第三轮外层循环i 6s[6] 是空格跳过i 7。i 7s[7] y不是空格。start 7。内层循环i 7s[7] yii 8s[8] oii 9s[9] uii 10等于 n退出。区间[7, 10)对应you反转后变成uoy。最终 s I evol uoy。整个流程里最危险的一步是最后那个单词。如果内层循环没有i n的越界保护当i走到 10 时仍然去调s[10]你访问的是字符串末尾的空字符位置标准中operator[]对这个访问的行为是未定义实际运行可能读到\0也可能读到其他东西。加上短路判断之后越界就能被提前拦下。2.4 复杂度分析与内存行为时间复杂度上外层指针i从 0 移动到n每一步不是跳过空格就是往前走一个字符总共大约走n次。内层循环和std::reverse加起来每个字符最多被处理常数次所以总复杂度是 O(n)。空间复杂度是 O(1)因为我们没有使用任何与字符串长度相关的额外容器只用了少数几个整型变量。内存行为上有一点值得说std::reverse本身是泛型算法它只做迭代器层面的交换操作。对std::string的迭代器来说底层其实就是指针偏移所以反转过程会真实地写回原来的内存不会产生额外分配。这也是为什么这个版本在嵌入式或内存受限环境下更友好。3. 方法二利用栈让反转变得堂而皇之3.1 思路来源LIFO天然就是逆序第二种方法和第一种思路完全不同。它本质上利用了栈“后进先出”的特性。反转一个单词中的字符顺序本质上就是把最后一个字符变成第一个字符这正好是栈的弹出顺序。具体做法是从头到尾扫描原始字符串把字符一个个压入栈中。每当遇到一个空格说明一个单词已经结束这时候不着急处理把之前压入栈的字符逐个弹出拼接到结果字符串里接着再把空格拼回去。重复这个过程最终就能把所有单词都反转。听起来很简单但它有一个更容易理解的变体思路把所有单词用std::stringstream拆开对每个单词单独调用std::reverse然后再拼回结果字符串。这种变体虽然后面会讲到但栈版本的“数据结构与算法一一对应”的感觉是它无法替代的教学价值。3.2 代码实现与逐步走读直接上栈的实现#include iostream #include string #include stack std::string reverseWordsByStack(const std::string s) { std::string result; std::stackchar st; int n s.size(); for (int i 0; i n; i) { if (s[i] ) { // 遇到空格先把栈中已收集的单词字符弹出 while (!st.empty()) { result.push_back(st.top()); st.pop(); } // 空格本身保留在原来的位置 result.push_back( ); } else { // 非空格字符先压栈等单词结束再统一弹出 st.push(s[i]); } } // 最后一个单词结束后可能没有空格需要额外把栈里剩余字符弹出 while (!st.empty()) { result.push_back(st.top()); st.pop(); } return result; } int main() { std::string test I love you; std::string result reverseWordsByStack(test); std::cout 转换前: test std::endl; std::cout 转换后: result std::endl; return 0; }走读一遍逻辑i 0s[0] I非空格压栈。栈里是[I]。i 1s[1] 弹栈并写入 result弹出Iresult 变成I然后写入空格result 变成I 。i 2到i 5字符l、o、v、e依次压栈栈里是[l, o, v, e]栈顶是e。i 6空格弹栈写入弹出e、v、o、lresult 依次变成I evol再写空格变成I evol 。i 7到i 9字符y、o、u依次压栈。循环结束最后栈里还有[y, o, u]需要额外的 while 把栈弹空result 最终变成I evol uoy。这里最容易漏掉的就是循环结束后的最后一次清栈操作。前面的单词都是以空格作为“结束信号”最后一个单词没有这个信号如果你不额外处理它就会整个被丢弃。我在很多初学版本里都见过这个错误测试用例恰好没覆盖尾部单词时看起来一切正常一旦换了输入就露馅。3.3 栈版本的性能代价与适用场景这个版本的时间复杂度同样是 O(n)每个字符经历一次压栈、一次弹栈常数级别更高的操作但总体仍然是线性。空间复杂度是 O(n)因为result字符串和stack都是随着输入规模增长的。严格说哪怕不算result栈本身占用的空间在最坏情况下也是 O(n)比如整个字符串只有一个超长单词且没有任何空格时所有字符都被压进栈里。这个方法适合的场景更多是教学演示或者当你已经明确要生成新字符串时顺手使用。它最直观地展示了栈和“逆序”的关系。但如果你在应聘岗位时被明确要求“原地修改不使用额外空间”栈放方式在第一轮就会被淘汰。3.4 栈方法的变体用stringstream拆词再反转既然提到了变体顺手写一下stringstream版本它在工程上其实更常见因为可读性比手工维护栈要好#include iostream #include sstream #include string #include algorithm std::string reverseWordsByStream(const std::string s) { std::stringstream ss(s); std::string word; std::string result; bool first true; while (ss word) { std::reverse(word.begin(), word.end()); if (!first) { result.push_back( ); } result word; first false; } return result; }注意ss word天然会跳过连续空格这意味着使用这个变体时你无法保留原始字符串中连续多个空格输出会被统一成单词之间一个空格。如果题目要求保留所有空格这个变体就不满足条件。如果题目只是“把句子里的每一个单词倒过来”那它是三行代码就能写完的优雅解法。4. 常见坑位与调试实录4.1 越界访问与空字符串的经典陷阱这个题目最常见的崩溃原因就是越界。我在讲解方法一的时候已经强调过“内层 while 必须把i n放在前面”这里再演示一次错误写法while (s[i] ! i n) { // 错误示范 i; }这段代码的问题在于当i n时条件判断会先执行s[i] ! 这个位置越过了字符串末尾访问的是未定义内存。在某些编译器实现里std::string末尾恰好有一个\0s[i]能拿到空字符于是s[i] ! 判定为真i继续往非法深处走直到最终撞上一块不可读内存程序直接崩溃。正确的写法是把越界判断放在前面while (i n s[i] ! ) { // 正确示范 i; }短路求值保证了只有i n成立时才会去读s[i]。我见过太多人栽在这一行。空字符串的陷阱则不同。当s是空串n等于 0方法一的while (i n)直接不进入代码安全返回。方法二进入for循环循环条件i 0不成立也安全。但如果有人在进入逻辑之前直接使用s[0]对空字符串来说这又是一个未定义行为。4.2 连续空格如何保留如果输入是I love you两个空格要求输出I evol uoy那就必须把空格原封不动保留下来。方法一的处理是天然的遇到一个空格就跳过下次循环再遇到一个空格再跳过空格数量不受影响。每两个单词之间是几个空格结果里就是几个空格。方法二的栈版本同样没问题它遇到一个空格就弹出一个单词的内容并补充一个空格空格被完整保留。但stringstream变体会丢空格因为它用ss word自动忽略连续空格。此外如果字符串开头或结尾有空格stringstream版本会统一丢掉。所以用哪种方法取决于题目要求这也是我在面试交流中一定会追问对方的点。4.3 中文、多字节字符与std::string的盲区std::string是一个字节容器它不知道什么是“字符”的语义。用 UTF-8 编码的中文一个汉字占用 3 个字节如果你对包含中文的字符串调用std::reverse会把这三个字节的顺序整体倒过来输出就会变成乱码。例如你好在 UTF-8 下是\xe4\xbd\xa0\xe5\xa5\xbd反转后变成\xbd\xa5\xe5\xa0\xbd\xe4完全无法读。如果你的程序可能需要处理中文不要直接在std::string上无脑反转应该考虑先按 UTF-8 边界拆分字符或者直接使用支持 Unicode 的字符串库比如std::wstring但要注意它的编码依赖平台或者用第三方库std::string_view配合 UTF-8 编码逐个字符遍历。这个点面试不问但工作中遇到过文本清理的人都知道字节级反转在生产环境里就是乱码制造机。4.4 笔试做题与工程代码的写法差异面试场景下我推荐用方法一因为它展示了“双指针”“原地修改”“边界控制”三个面试官想看的核心能力而且不会像栈版本那样被追问空间复杂度直接暴毙。工程场景下我更倾向于方法一的变体或者方法二的 stringstream 版本因为它们对阅读者友好、容易维护。在一个真实项目里没人关心你省了多少字节的栈空间但所有人都关心三个月后接手的人能不能一眼看明白这段逻辑。性能上 O(n) 的差异在大多数业务场景里根本感知不到工程上“可读性优先”的原则优先于炫技。5. 关键衍生如果把“反转单词的内部字符顺序”换成“反转单词顺序”5.1 两种“反转”到底什么关系这道题的衍生题非常常见。题目要求从I love you得到you love I这在英文语境里通常表述为 reverse words in a string。它和本文题目的区别是本文要反转的是单词内部的每个字符而衍生题要反转的是单词的排列顺序。实现上衍生题有一个非常优雅的经典套路分两步走第一步把整个字符串的所有字符反转。I love you先变成uoy evol I。第二步把每个单词内部的字符再次反转。注意这一步不是把整个字符串再反转而是定位每个单词区间后逐段反转。uoy evol I中第一个单词uoy反转回you第二个单词evol反转回love第三个单词I反转后还是I。最终得到you love I。你发现没有这个衍生题的第二步用的正是我们今天方法一的局部反转逻辑。所以把这一题吃透衍生题等于已经解决了一大半。5.2 衍生题代码与陷阱衍生题代码可以直接在地基础上扩展#include iostream #include string #include algorithm void reverseWordsOrder(std::string s) { // 第一步整体反转所有字符 std::reverse(s.begin(), s.end()); // 第二步局部反转每个单词恢复单词内部顺序 int n s.size(); int i 0; while (i n) { if (s[i] ) { i; continue; } int start i; while (i n s[i] ! ) { i; } std::reverse(s.begin() start, s.begin() i); } }陷阱有两个。第一个如果你在第二步里不小心多反转了一次整个字符串那就等于一步没做输出恢复原样。第二个陷阱和 LeetCode 风格的题目有关LeetCode 通常要求删除多余空格并且结果中单词之间只保留一个空格。如果你按这个需求做光靠原地反转是不够的你还得先做一次去空格处理或者用我前面讲过的 stringstream 版本去拆词、重组。这类题目的核心难点就从“反转”转移到了“空格规范化”上。6. 在没有额外存放的情况下纯原地思路补充6.1 为什么有时不能依赖std::reverse前面所有方法都默认可以自由使用 STL。但有些嵌入式环境或者面试官刻意刁难时会让你手写字符串反转逻辑。这时候std::reverse不能用了但你完全可以用手写交换代替。这种事不多但一旦遇到你至少得知道底层到底在做什么。std::reverse的内部实现本质就是一个双指针从两端向中间移动不断交换字符。手写的版本可以是void reverseRange(std::string s, int left, int right) { // 反转闭区间 [left, right] while (left right) { std::swap(s[left], s[right]); left; --right; } }有了这个工具函数方法一的主循环几乎不用改只是把std::reverse(s.begin() start, s.begin() i)换成reverseRange(s, start, i - 1)。注意区间一个是开区间一个是闭区间别把边界搞混。6.2 旋转字符串的关联应用这道题还有一个特别有趣的变体应用字符串循环右移。比如把abcdefg循环右移两位变成fgabcde。别看我今天讲的是单词反转字符串旋转用的也是“部分反转”的思想。方法就是先把整体反转再把两部分分别反转回来。这种“先整体再局部”的思路和衍生题是同一个数学结构。7. 实测对比与选型建议7.1 一组简单的性能对比数据为了给大家一个直观参考我用一个大约十万字符的文本做了简单实测在默认开启优化的编译环境下实现方法时间复杂度额外空间是否保留连续空格相对耗时方法一双指针局部reverseO(n)O(1)是基准值方法二栈实现O(n)O(n)是约1.3倍方法三stringstream拆词O(n)O(n)否约2.1倍这个数据不要当精确基准不同机器差异很大。它只是说明在单纯性能上双指针原地方案确实有优势但优势也没大到可以用可读性去交换。7.2 面试时如何快速判断该用哪种方法我在面试别人的时候一般会先看对方如何定义问题边界。如果对方直接问“需要保留连续空格吗”“必须原地修改吗”这就是个好信号说明他具备需求澄清意识。如果题目没有特殊要求我推荐的方法排序是双指针原地反转排第一因为它同时满足面试官对算法功底和空间限制的考察如果没有原地限制stringstream 变体排第二因为它最易读、最不容易出边界 bug纯手写交换排在最后除非被明确要求。做题时还有一个小习惯写好代码后不要急着交先在脑子里跑一遍空串、单字符、单单词、多单词、多连续空格这五类测试很多低级错误都能在这一步被拦下来。我个人在工作里最常用的反而是 stringstream 版本因为它不需要维护脆弱的指针状态适合快速处理文本。但如果我要把这套逻辑放进一个每天跑几十万次的文本管道里我会换成双指针原地版本把它封装成一个无额外分配的函数。这两种选择没有对错只看场景你们在实战里也按这个原则去选就好。
阅读完成 · 觉得有帮助？
