力扣151 - 反转字符串中的单词【双指针与字符串的火花】

Hello大家好，这是一道在字符串题目中有关双指针解法的题目，属于比较经典又有操作性和复杂度的例题，因而拿出来做讲解，详细介绍送给大家💝

一、原题描述

原题传送门
给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：

输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

二、思路分析

1、题型引入

• 之前有做过一道题叫做力扣344.反转字符串，也是利用双指针的写法对一个字符串进行操作，题目的思路就是使用双指针不断地从两端向中间移动，然后依次互换两头的字符，因为只需要颠倒两头的字符，因为当两个双指针移动到中间时，即交换完毕

代码很简洁，知道思路有了，双指针的代码并不难写，C/C++代码如下🌾

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left  = 0;
        int right = s.size() - 1;
        while(left < s.size()/2)
            swap(s[left++],s[right--]);
    }
};
1
2
3
4
5
6
7
8
9

2、思路分析

• 通过上一题字符串的翻转的引入，相信大家对双指针如何在字符串中进行使用已经有了一个初步的了解，但是本题却没有那么容易，不然我也不会拿出来作为经典例题讲解
• 首先看题目本身，给到一个字符串s,要返回的是字符串中单词的顺序，这里要注意，不是和上一题一样将一个子串做颠倒，而是整体性地进行一个翻转，这就需要我们去分步骤讨论和分析。还有一点要注意的是给出的目标串可能子串单词不一定只会有一个空格，也可能会有多个空格，这是我在调试运行的时候观测到的一点，而且这个s串可能还具有前导空格和尾部空格，这些都需要我们去考虑到，怎么样，是不是感觉一下子又要头脑风暴了🌊

---

• 好，我们来大体地说一下整体的这个思路
  ①去除给出的目标串中多余的空格
  ②将整个字符串做一个反转
  ③逐个去将其中的子串单词一一翻转
  ④完成单词的翻转

想知道如何实现这几步吗，那就听我娓娓道来🔍

三、代码详解

1、分步骤解析

（1）移除给出字符串中的多余空格（Wonderful）

• 首先就是第一步，移除给出字符串中的多余空格，这是第一步也是最关键的一步🔑因为只有在没有多余其他空格的干扰下才可以做整体翻转和局部翻转的可能
• 【题外话】在力扣中这个题目中并给出这个空间复杂度的限制，这样就可以自己再开辟一个字符串做放置移位操作。而且随着现在字符串库函数的越加丰富，对于字符串的操作几乎不用自己思考，只需要调用一下API即可，所以大家都调侃自己时API调用工程师，确实，有些API在开发的时候是可以给我们带来便利，但是在刷题的过程中，我们看到一个操作就立马想到用API去解决，而且这道题的核心代码用API可直接解决，那就失去了刷题的意义，像这题你完全可以用Java中String类的split()，去分割单词，然后定义一个新的string字符串，最后再把单词倒序相加，你要这样做那这就是道水题，没有任何意义
• 好的，言归正传，插了一些小话题，我们规定空间复杂度就只能是O(1)，那么你就不可以再去使用辅助空间了，只能在原字符串中下功夫，这就可以想到我们的双指针解法了，还记得吗，我在力扣27 - 移除元素【双指针】中说到如何使用双指针循环交替换位去做消除元素的操作，这里其实也是一样的，那一题是消除元素，那这一题就是把元素换成空格而已
• 但是有些小伙伴很单纯，就是用一个for循环去遍历字符串s，然后遇到空格就用erase()删除一下。哈哈，确实，这就是很直白的写法，我也可以给代码,从如下代码可以看出，我是将移除空格分为了三个部分，分别是
  ①移除字符串当中的多余空格
  ②移除前导空格
  ③移除尾随空格
• 但是你以为这只是O(n)的时间复杂度吗，不，erase()这个API的底层实现就已经是O(n)，然后外面在用一个for循环去遍历字符串，按就是O(n²)的时间复杂度，虽然是很清晰地分步骤解决了问题，但是却无故中增加了时间复杂度，而你自己可能还不知道

void removeExtraspaces(string& s)
{
    //移除字符串当中的多余空格
    for(int i = s.size() - 1;i > 0; --i)
    {
        if(s[i] == s[i - 1] && s[i] == ' ')
            s.erase(s.begin() + i);
    }

    //移除前导空格
    if(s.size() > 0 && s[0] == ' ')
        s.erase(s.begin());
    
    //移除尾随空格
    if(s.size() > 0 && s[s.size() - 1] == ' ')
        s.erase(s.begin() + s.size() - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• Ok，不多讲，我们的重点在于双指针，如何用双指针去除空格呢，上面说了，这就和移除元素是一个道理
• 快指针fast：用来获取新数组中的元素，即不为空格的位置
• 慢指针slow：获取新数组中需要更新的位置

先行给出C++代码

void removeExtraSpaces(string& s)
{
    int slow = 0;
    for(int fast = 0;fast < s.size(); ++fast)
    {
        if(s[fast] != ' ')      //当快指针指向不为空格时，进行互相替换
        {
            if(slow != 0)   //解决每个单词之间的空格
                s[slow++] = ' ';

            //若slow当前为0，则直接替换，为了解决前导空格
            while(fast < s.size() && s[fast] != ' ')
                s[slow++] = s[fast++];      //指针元素互换，直到一个单词结束
        }
    }
    s.resize(slow);     //慢指针当前所指位置即为去空格后数组大小
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

交替过程展示

还是一样，一张张分部图解手撕算法，为的是能让大家看清指针走的每一步，所以不要怕麻烦，跟着我一步一步来🚶

①首先，只有当fast快指针指向不为空时才做，交替，但一开始快指针指向首除，因此不进if(s[fast] != ’ ')的判断，fast快指针直接后移

②若快指针遍历到不为空，与慢指针进行替换，此处进入的是这个while循环，而不是if(slow != 0)这个判断，因为此时慢指针是指向位置0的，所以直接进行交替即可，也就是这样的操作，可以代替erase()的那一小部分的前置空格的操作

while(fast < s.size() && s[fast] != ' ')
    s[slow++] = s[fast++];      //指针元素互换，直到一个单词结束
1
2

③接下来注意了，这是一个while循环，此时并没有跳出这个while循环，因为快指针还没有遍历到空格而且快指针还没到达末尾，所以在上一次替换之后，双指针后移，继续进行一个替换操作，这时候第二个字母e就被继续替换
- 这个单词while循环后面是一样的操作，不做赘述，进入关键一步🔑
④在交替放置完字母o之后，双指针同时后移，这时候快指针碰到了空格，即跳出while循环

⑤这个时候回到最初的大循环，fast指针后移一位，发现后面还是空格，所以再移动一位，这个时候边碰到了字母w，进入if(s[fast] != ’ ') 这个if分支的判断

for(int fast = 0;fast < s.size(); ++fast)
1

• 由于此时慢指针slow已经不是处于位置0了，所以将会进入这个if分支的判断，这个写法是C++中的写法，上述也有用到过，可以把slow++单独再拿出来，这样写只是为了美观简练而已，具体的意思是将慢指针slow当前位置置为空，然后慢指针后移一位，是为了解决每个单词之间的空格问题，

if(slow != 0)   //解决每个单词之间的空格
    s[slow++] = ' ';
1
2

⑥接着就是下一个单词的交替赋位，从下图可以看出，#hello#和#world#之间是有一个空格的，很好的解决了前面的所有空格

⑦最后一步，就是解决最后面的后置空格了，此时在字母’d’赋位完后，双指针同时向后移动，快指针fast便指向了空，所以不进入任何分支判断，fast指针继续后移，超出字符串边界，自动结束外层for循环的遍历，此时进行这一步操作，使用resize()函数重新开始数组空间，慢指针slow当前所指位置即为新数组大小

s.resize(slow);     //慢指针当前所指位置即为去空格后数组大小
1

这就是去除所有空格后的结果，大家在做完一个功能之后就可以点击#执行代码#看看是否成功

• 这还只是第一步，感受到这道题的魅力了吗🔥

（2）反转整个字符串

好，接下来我们进入第二步，也就是在去除了多余空格后，我们需要将整个字符串进行一个反转，其实这个就是开头讲到的那道题

void reverseString(string& s,int start,int end)
{
   for(int i = start,j = end;i < j;++i,--j)
       swap(s[i],s[j]);
}
1
2
3
4
5

• 当然大家也可以直接用reverse()算法，交换，这个算法我在C++ STL【常用算法】详解中有过详细介绍，如果不清楚的小伙伴可以去看看

这是反转后的样子，可以看出，就差把单个单词进行逐一翻转了

（3）反转单个单词

好的，最后就来到了我们反转单个单词的部分，加油，快爬到山顶了⛰

//3.反转单个单词
int start = 0;      //标记每个单词的起始位置
for(int i = 0;i <= s.size(); ++i)
{
                        //直到遍历到一个空格位置才算结束一个单词
    if(i == s.size() || s[i] == ' ')
    {   //i == s.size() - 遍历到最后一个单词的末尾要单独判断，因为其后无空格

        reverseString(s,start,i - 1);       //反转单词
        start = i + 1;      //更新下一个单词的起始位置
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

• 首先我们需要定义一个变量去保存每次下一个单词的起始位置，因为这个起始位置随着指针的移动每次都会发生变化
• 然后就是去循环中遍历这个目标串s，这里的for循环为什么要遍历到s.size()呢，因为我们遍历到最后一个单词时后方已经没有空格了，所以这个情况需要单独判断，而分隔每个单词的条件就是遍历到s[i] == ’ '，这个时候表示一个单词已经遍历完毕，调用我们上面的

reverseString(s,start,i - 1);
1

• 去反转这个子串即可实现我们所要的效果，然后为什么要start = i + 1这个操作呢，因此此时你反转子串单词的时候i是处于空格的位置，但是下一个单词要从首字母开始，所以i + 1就是移动到下一个单词的初始位置，将其保存在start中，每次反转子串时我们传入的初始位置就是start

2、整体代码展示

class Solution {
public:
    void removeExtraSpaces(string& s)
    {
        int slow = 0;
        for(int fast = 0;fast < s.size(); ++fast)
        {
            if(s[fast] != ' ')      //当快指针指向不为空格时，进行互相替换
            {
                if(slow != 0)   //解决每个单词之间的空格
                    s[slow++] = ' ';

                //若slow当前为0，则直接替换，为了解决前导空格
                while(fast < s.size() && s[fast] != ' ')
                    s[slow++] = s[fast++];      //指针元素互换，直到一个单词结束
            }
        }
        s.resize(slow);     //慢指针当前所指位置即为去空格后数组大小
    }

    void reverseString(string& s,int start,int end)
    {
        for(int i = start,j = end;i < j;++i,--j)
            swap(s[i],s[j]);
    }
    string reverseWords(string s) {
        //1.移除给出字符串中的多余空格
        removeExtraSpaces(s);

        //2.反转整个字符串
        reverseString(s, 0, s.size() - 1);

        //3.反转单个单词
        int start = 0;      //标记每个单词的起始位置
        for(int i = 0;i <= s.size(); ++i)
        {
                                //直到遍历到一个空格位置才算结束一个单词
            if(i == s.size() || s[i] == ' ')
            {   //i == s.size() - 遍历到最后一个单词的末尾要单独判断，因为其后无空格

                reverseString(s,start,i - 1);       //反转单词
                start = i + 1;      //更新下一个单词的起始位置
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

四、回顾总结

本题的讲解到这里就结束了，怎么样，这波字符串与双指针的搭配有没有震撼到你，原来双指针还可以这么去操纵字符串，如果您对讲解的哪处有所疑问，可以于评论区或者私信我，感谢您对本文的观看🌹

以下是在剑指Offer里相关的题型，在看完本题可以去继续去练练手

剑指Offer 05.替换空格
剑指Offer58-II.左旋转字符串