151.反转字符串中的单词

发表于： 2023-07-29 分类于： leetcode

字数： 1537 阅读：≈ 4分钟

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

给你一个字符串 s ，请你反转字符串中单词的顺序。

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

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

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

思路

基本思想

为了实现单词的翻转，需要借鉴左旋转字符串的思想，为了实现单词的逆转，需要先将单词逆转，然后在逆转整个字符串，但是不能直接逆转，需要去除多余的空格，所以整个问题分为两个解决步骤：

去除多余的空格，但是每个单词之间需要保留一个空格

为了实现这个功能，第一个单词之前不能加空格，所以需要两个指针解决问题，一个指针找到单词的起点，然后一个指针接受单词，将空格覆盖

接受单词之前，需要判断是否需要加上一个空格作为单词之间的间隔

一旦找到一个单词的起点，就一次性将整个单词取出，具体的代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
//去除单词中的多余空格
int fast=0,slow=0;
for(;fast<s.size();++fast){
    //找到单词开头
    if(s[fast]!=' '){
        //单词之间增加一个空格
        if(slow!=0){
            s[slow++]=' ';
        }
        //将单词取出来
        while(fast<s.size()&&s[fast]!=' '){
            s[slow++]=s[fast++];
        }
    }
}

去除多余的空格之后，就是完成单词的反转，此时就和左旋转字符串的思想一致了，先逆转每个单词，然后将字符串整体逆转

每个单词的逆转需要找到单词的位置，记住起始位置和结束位置，因为最后一个单词不能用空格判断单词的结束，只能通过判断当前下标是不是字符串的末尾

所以需要统一交换的区间，区间为左闭右闭时，判断到单词的结尾需要传递上一位置，区间为左闭右开时，直接传递当前位置

具体的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
//翻转每一个单词
int start=0;
for(int i=0;i<=slow;++i){
    //走到最后一个单词或者中间的单词
    if(s[i]==' '||i==slow){
        swap(s,start,i-1);
        start=i+1;
    }
}
//字符串整体翻转
swap(s,0,slow-1);

返回最终的结果
返回时只需要返回给定的范围即可，不是直接将整个字符串返回
1
return s.substr(0,slow);

新的思路

根据以上分析，其实就是两个步骤，去掉多余的空格和将后面的单词拿到前面，而去掉多余的空格可以转换成拿出有效的单词，并且拿出有效的单词之后，可以使用头插法来形成最终的结果，这样单词拿完之后，整个字符串也逆转了

注意在每个单词拿完之后，单词与单词之间需要加一个空格，加空格的时机是下一个有效单词被取出来之后，加入到结果字符串序列之前

执行流程

去除多余的空格
1. 找到单词开头
2. 取出整个单词
3. 单词之间保留一个空格
反转单词
1. 找到每个单词的开始和结束
2. 向反转函数传递范围并翻转
反转整个字符串
返回指定范围的字符串

根据新的思路得到的执行流程如下：

遍历字符串，遇到一个有效字符就开始拿单词
拿到一个单词之后，将其加入到结果字符串中
加入时需要判断当前字符串中有没有单词，有的话需要给两个单词之间加一个空格
加入单词时使用头插法

代码

根据以上分析，得出以下代码：

 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
class Solution {
public:
    string reverseWords(string s) {
        //去除单词中的多余空格
        int fast=0,slow=0;
        for(;fast<s.size();++fast){
            //找到单词开头
            if(s[fast]!=' '){
                //单词之间增加一个空格
                if(slow!=0){
                    s[slow++]=' ';
                }
                //将单词取出来
                while(fast<s.size()&&s[fast]!=' '){
                    s[slow++]=s[fast++];
                }
            }
        }
        //翻转每一个单词
        int start=0;
        for(int i=0;i<=slow;++i){
            //走到最后一个单词或者中间的单词
            if(s[i]==' '||i==slow){
                swap(s,start,i-1);
                start=i+1;
            }
        }
        //字符串整体翻转
        swap(s,0,slow-1);
        return s.substr(0,slow);
    }
    void swap(string &s,int begin,int end){
        for(int i=begin,j=end;i<j;++i,--j){
            char temp=s[i];
            s[i]=s[j];
            s[j]=temp;
        }
    }
};

按照新思路得到的代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    //1. 去除多余的空格
    //2. 翻转每一个单词
    public String reverseWords(String s) {
        //去除多余的空格
        String str="";
        for(int i=0;i<s.length();++i){
            //遇到一个不为空的字符就是遇到了一个单词，将其取出来，前后加上空格
            if(s.charAt(i)!=' '){
                String temp="";
                while(i<s.length()&&s.charAt(i)!=' '){
                    temp+=s.charAt(i++);
                }
                //拿到一个单词之后，直接头插法进行逆转
                //注意单词与单词之间需要加一个空格
                if(str!="")
                    str=" "+str;
                str=temp+str;
            }
        }
        return str;
    }
}

总结

主要是需要将问题分解，先去除多余的空格，然后在模拟单词和字符串的反转

以上两步可以合并到一起，去除多余的空格就是拿到有效单词，之后直接头插法就可以字符串反转