跳到主要内容

LeetCode 151. 反转字符串中的单词

本节目标

提取有效单词、逆序并用单个空格连接，完成空白规范化。

这道题使用单词与映射解题框架的文本规范化流程：先把输入变成词序列，再逆序，最后统一输出格式。

查看原题

朴素思路及瓶颈​

逐个字符从右向左拼接也能完成反转，但必须反复处理首尾空格、连续空格和单词边界，容易在字符串前部插入时产生平方级移动。提取单词后逆序，逻辑更直接，也天然完成空白归一化。

空白归一化不变量​

提取阶段的 words 只保存非空单词，因而忽略首尾空白并折叠中间连续空白。逆序后，结果在连接前保存完整单词；连接时只在两个相邻单词间加入一个空格。空输入或全空白输入会得到空字符串，单词 hello 则保持不变。

代码实现​

C++ 用流提取单词，Python 用 split()；两者都遵循“提取单词 → 逆序 → 单空格连接”，没有对原串进行脆弱的原地修改。

C++17
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        istringstream parser(s);
        vector<string> words;
        string word;
        while (parser >> word) {
            words.push_back(word);
        }

        reverse(words.begin(), words.end());
        string result;
        for (size_t index = 0; index < words.size(); index++) {
            if (index > 0) {
                result += ' ';
            }
            result += words[index];
        }
        return result;
    }
};

复杂度分析​

  • 时间复杂度：O(n)，扫描、逆序和连接都为线性。
  • 空间复杂度：O(n)，用于保存单词和结果。

易错点​

  • 用 split(' ') 后没有删除空字符串。
  • 只反转整个字符串，导致每个单词内部的字符也被反转。
  • 输出时保留输入的多余空白，违反单空格连接要求。

模式迁移​

这个流程可迁移到日志字段、命令行参数和简单文本清洗：先定义 token，再决定 token 的顺序与输出分隔符。若分隔规则含引号或转义，需要升级为显式词法分析器。