【面试经典 150 | 数组】反转字符串中的单词

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：模拟实现
- 方法二：使用库函数
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【字符串】【字符串分割】

题目来源

151. 反转字符串中的单词

解题思路

方法一：模拟实现

思路

一个朴素的解题思路是根据空格将字符串分割成一个个的字符串，然后 oush_back 到 vector 容器中，最后反转容器，再用单个空格将字符串拼接起来。

利用 vector 容器以及反转这两次操作可以换成 deque 的 push_front 操作，充分双端队列两端都可以插入数据的特性。

以下代码使用的是 vector 容器。

首先利用 while 循环将字符串 s 的头部和尾部的出现的空格去除。实际上是用双指针模拟去除的，经过处理后 l 和 r 指针分别指向字符串 s 中第一个非空字符和最后一个非空字符。

接着在 [l, r] 之间遍历字符，如果遇到非空字符就将该字符加入到临时字符串 word 中，如果遇到一个空格且 word 不为空，则将 word push 到字符串数组 tmpStr 中。因为字符串 s 中间可能会有多个空格，我们这样操作的目的是只有在字符串 word 之后遇到第一个空格，才会将 word 加入 tmpStr。如果题目中说明字符串中间有空格只会是单个空格，则此处就不需要判断 word 不为空。

注：一定不能忘记，字符串中的最后一还没有加入到 tmpStr 中。

最后，反转字符串数组 tmpStr，并用单个空格将反转后字符串数组中的字符拼接起来。

代码

class Solution {
public:
    string reverseWords(string s) {
        int l = 0, r = s.size()-1;
        while(l <= r && s[l] == ' ') ++l; // 模拟去除字符串头部出现的空格   
        while(l <= r && s[r] == ' ') --r; // 模拟去除字符串尾部出现的字符
        
        vector<string> tmpStr;
        string word = "";
        for (int i = l; i <= r; ++i) {
            if (!word.empty() && s[i] ==' ') {
                tmpStr.push_back(word);
                word = "";
            }
            else if (s[i] != ' ') {
                word += s[i];
            }
        }
        tmpStr.push_back(word);

        reverse(tmpStr.begin(), tmpStr.end());
        string res = "";
        for (int i = 0; i < tmpStr.size(); ++i) {
            res += tmpStr[i];
            if (i != tmpStr.size() - 1) {
                res += ' ';
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 为字符串 s 的长度。

空间复杂度： $n$ 。