0151. Reverse Words in a String

题目信息

题号:
  1. 反转字符串中的单词

难度:

Medium

主题:

字符串、双指针、原地压缩、区间反转

原题:

LeetCode 0151

重点:

先把空格规则归一化,再用整体反转改变单词顺序、逐词反转恢复单词内部顺序

题目重述

给定字符串 s,其中单词是连续非空格字符组成的最大片段。返回单词出现顺序完全反转后的字符串。输入 可能有前导、尾随和连续多个空格;输出只保留原单词,相邻单词间恰好一个空格,首尾没有空格。输入保证 至少含一个单词。

自建示例

  • "   code   reads  clearly " 变为 "clearly reads code";

  • "one" 仍为 "one",不产生额外空格;

  • "  a   bc " 先规范为空格单一的 "a bc",再得到 "bc a",单词内部字符不能反转。

C++ 实现

#include <algorithm>
#include <string>
#include <utility>
#include <vector>

class Solution {
private:
    std::string collectWordsThenJoin(const std::string& s) {
        std::vector<std::string> words;
        const int length = static_cast<int>(s.size());

        for (int read = 0; read < length;) {
            while (read < length && s[read] == ' ') {
                ++read;
            }
            if (read == length) {
                break;
            }
            const int start = read;
            while (read < length && s[read] != ' ') {
                ++read;
            }
            words.push_back(s.substr(start, read - start));
        }

        std::string result;
        for (int index = static_cast<int>(words.size()) - 1;
             index >= 0;
             --index) {
            if (!result.empty()) {
                result.push_back(' ');
            }
            result += words[index];
        }
        return result;
    }

    std::string compactAndReverse(std::string s) {
        const int originalLength = static_cast<int>(s.size());
        int write = 0;

        for (int read = 0; read < originalLength;) {
            while (read < originalLength && s[read] == ' ') {
                ++read;
            }
            if (read == originalLength) {
                break;
            }
            if (write > 0) {
                s[write] = ' ';
                ++write;
            }
            while (read < originalLength && s[read] != ' ') {
                s[write] = s[read];
                ++write;
                ++read;
            }
        }
        s.resize(write);

        std::reverse(s.begin(), s.end());
        for (int start = 0; start < write;) {
            int end = start;
            while (end < write && s[end] != ' ') {
                ++end;
            }
            std::reverse(s.begin() + start, s.begin() + end);
            start = end + 1;
        }
        return s;
    }

public:
    std::string reverseWords(std::string s) {
        return compactAndReverse(std::move(s));
    }
};

题解

原始方案:先把单词变成独立对象

最直接的 collectWordsThenJoin 扫描出每个最大非空格片段,放进 words,再从数组末尾向前拼接。它 把“识别单词”“反转顺序”“规范空格”分成清晰步骤,正确性直接;代价是同时保存单词数组、各个子串和最终 字符串,额外存储与输入长度成正比。

题目返回字符串本身已经提供一块可写缓冲区。若能在其中先得到规范单词序列,再利用区间反转改变排列,就 不必保存单词列表。

第一阶段:读写指针只保留逻辑内容

read 在原内容上跳过全部空格,再复制一个完整单词;write 指向规范结果的下一个位置。除第一个单词 外,每写新单词前只写一个空格。扫描结束后把字符串缩到 write,便同时删除了前导、尾随和重复空格。

循环开始处理某个单词时,write 不会越过 read:前面删除过的空格只会让写指针更靠左;两个单词 之间至少有一个已被 read 跳过的空格,所以先写规范分隔符也不会覆盖尚未读取的单词首字符。原地向前 复制因此安全。

这个阶段结束后的不变量是:s[0..write-1] 恰好按原顺序包含所有单词,单词间一个空格,首尾无空格。 后续反转无需再判断多余空格。

两类反转怎样只改变单词顺序

整体反转规范字符串,会同时发生两件事:单词块顺序倒置,每个单词内部字符也倒置。第二次扫描以空格为界, 逐个反转每个单词区间,只恢复内部字符顺序,不改变块的位置。因此最终只剩单词顺序的反转。

规范化:     "code reads"
整体反转:   "sdaer edoc"
逐词恢复:   "reads code"

空格是单字符分隔符,整体反转后仍然位于两个反向单词块之间;逐词反转的区间不包含空格,所以输出继续满足 间隔规则。

逐词扫描的边界

start 指向当前单词首字符,end 前进到空格或字符串末尾;reverse(begin+start, begin+end) 使用 左闭右开区间。完成后令 start = end + 1 跳过分隔空格。最后一个单词使 end == write,新的 start 虽为 write + 1,循环条件立即失败,不会解引用越界。输入至少有一个单词,所以压缩结果非空。

为什么不用逐个搬移单词

若每次把最后一个单词移到输出前方,字符串中间插入会反复移动后续字符,最坏形成二次工作。整体反转把 所有单词块的位置一次性互换,逐词反转又只访问每个字符一次;没有任何单词需要单独跨越其他单词。

主解选择与复杂度

公开入口采用原地压缩加两类反转。每个字符参与常数次扫描或交换,时间 O(n);在传入的返回字符串缓冲 上操作,除返回值自身外只用固定下标,工作空间 O(1)。分词数组方案同为线性时间,但额外空间 O(n),保留它作为题目规则的直观基线;主解利用反转结构删除了单词数组与拼接状态。