7、反转字符串中的单词【⭐】

看了这么多简单题，我们来看一道中等题:car:

① 题目描述：

力扣原题

② 思路分析：

• 首先我们可以知道的是本题也是在反转一些东西，但反转的不是整个字符串，而是字符串中的每个单词，这就使有些同学感到些许疑惑了(・∀・(・∀・(・∀・*)，让我反转整个字符串还行，就单体地反转里面的一部分，而且还得保持这个单词的顺序不能错乱
  
• 不仅如此，题目中还给出了这么一句话
  注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格
  
• 也就是下面这种，因此呢我们还要去考虑到字符串的前面、后面以及各个单词中间存在空格的情况
  

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

💬 那经过我上面这一说相信很多同学都懵逼了，那到底这道题该如何去做呢？

• 我大概把具体的步骤分为以下几步：

1. 去除给出的目标串中多余的空格
2. 将整个字符串做一个反转
3. 逐个去将其中的子串单词一一翻转
4. 完成单词的翻转

接下去我们就来分步骤地讲解一下

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

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

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);
}

• 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);     //慢指针当前所指位置即为去空格后数组大小
}

交替过程展示

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

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

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

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

③  接下来注意了，这是一个while循环，此时并没有跳出这个while循环，因为快指针还没有遍历到空格而且快指针还没到达末尾，所以在上一次替换之后，双指针后移，继续进行一个替换操作，这时候第二个字母e就被继续替换

💬 这个单词while循环后面是一样的操作，不做赘述，进入关键一步:key:

④ 在交替放置完字母o之后，双指针同时后移，这时候快指针碰到了空格，即跳出while循环

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

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

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

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

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

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

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

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

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

（2）反转整个字符串

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

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

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

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

（3）反转单个单词

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

// 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;      // 更新下一个单词的起始位置
    }
}

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

reverseString(s,start,i - 1);

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

③ 代码展示：

• 来看下整体的代码吧

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;
    }
};

④ 运行结果：

• 从运行结果来看本算法也比较高效

8、反转字符串中的单词|||

本题的话如果你在做了上一题的话是完全没问题的，看看就知道了👀

① 题目描述：

力扣原题

② 思路分析：

• 相信你在看了题目之后已经知道怎么做了，因为这就是我们上一题所完成的第三步，此处便不做详解

③ 代码展示：

• 怎么样，看着代码是不是很眼熟

class Solution {
public:
    void ReverseStr(string& s, int begin, int end)
    {
        for(int i = begin, j = end; i < j; ++i, --j)
        {
            swap(s[i], s[j]);
        }
    }
    string reverseWords(string s) {
        int start = 0;
        for(int i = 0;i <= s.size(); ++i)
        {
            if(i == s.size() || s[i] == ' ')
            {
                ReverseStr(s, start, i - 1);
                start = i + 1;
            }
        }
        return s;
    }
};

④ 运行结果：