题目 leetcode151

题目链接 https://leetcode.cn/problems/reverse-words-in-a-string/

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
示例 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

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
48
49
50
51
class Solution {
public:
    //从begin开始找到下一个空格的下标，不包括begin本身
    int find_space(string&s,int begin=0)
    {
        int i=0;
        for(i=begin+1;i<s.size();i++)
        {
            if(s[i]==' '){
                return i;
            }
        }
        return s.npos;
    }

    string reverseWords(string s) {
        int i=0;
        vector<string> v;//用来存放单词
        for(i=0;i<s.size();i++)
        {
            // 跳过前导空格
            while(s[i]==' '){
                i++;
            }
            // 如果已经到最后面了，就直接跳出
            if(i>=s.size()){
                break;
            }
            int index = find_space(s,i);
            int sz = index-i;//单词长度
            //cout << i << " | " << index << " | "<< sz << endl;
            string temp(s,i,sz);
            //cout << temp << "-" << endl;
            v.push_back(temp);//插入单词
            i = index-1;//跳过当前单词
        }
        //反向迭代器
        auto it = v.rbegin();
        string ret = "";
        while(it!=v.rend())
        {
            ret+=*it;
            // 不是倒数第一个才加空格
            if(++it!=v.rend()){
                ret+=" ";
            }
        }
        cout << ret << endl;
        return ret;
    }
};

上面的办法中，新增了一个vector来拼接字符串，空间复杂度O(N)

测试 4MS 7.2MB

方案2

进阶要求：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//版本2，原地算法吗？
class Solution {
public:
    #define SEP '|'
    //从begin开始找到下一个空格的下标，不包括begin本身
    int find_space(string&s,int begin=0)
    {
        int i=0;
        for(i=begin+1;i<s.size();i++)
        {
            if(s[i]==' '){
                break;
            }
            else if(s[i]==SEP)
            {//用一个特殊字符作为原字符串结尾
                break;
            }
        }
        //如果是因为找到空格跳出，判断该字符串后面还有没有有效字符
        int k = i;//不能改i
        if(s[k]!=SEP)
        {
            while(s[k]==' ')
            {
                k++;
                //一直走到了|，代表没有有效字符了
                if(s[k]==SEP){
                    return s.npos;
                }
            }
            //走到这里代表有
            return i;
        }

        return s.npos;
    }

    string reverseWords(string s) {
        int i=0,end_word=0,index=0;
        int begin_sz = s.size();//起始大小
        s+=SEP;//用一个特殊字符作为原字符串结尾
        int sep_index = s.size()-1;//最后一个字符的位置就是分隔符
        
        for(i=0;i<begin_sz;i++)
        {
            // 跳过前导空格
            while(s[i]==' '){
                i++;
            }
            // 如果已经到最后面了，就直接跳出
            if(i>=begin_sz){
                break;
            }
            index = find_space(s,i);
            //如果找不到下一个空格了，代表当前是原字符串最后一个单词
            //跳过
            if(index == s.npos){
                end_word=i;
                break;
            }
            int sz = index-i;//单词长度
            string temp(s,i,sz);
            temp+=" ";
            //不能尾插，应该在sep之后插入
            //s += temp;
            s.insert(sep_index+1,temp);

            // cout << i << " | " << index << " | "<< sz << endl;
            // cout << temp << "-" << endl;

            //构造了之后，把原str这部分删了(错误！删了之后下标变了，循环无意义)
            //s.erase(i,sz);

            i = index-1;//跳过当前单词
            //index-1是因为本次循环过了之后会被for给+1
        }
        cout <<"[end]"<< s << endl;
        // 字符串中添加的|替换为空格
        index = s.find(SEP);
        
        // 删除index之前,end_word之后的空格
        int k = s.find(" ",end_word);
        //cout << "k:" <<k<<" endw:" << end_word <<endl;
        if(k!=s.npos&&k<index){
            s.replace(k,1,"");
            index--;
            //cout <<"[while1]k:"<<k <<" str:"<< s << endl;
            //因为替换过了之后，k的位置变成了原有k的下一位
            //此时如果k还是空格，代表原字符串末尾有多个空格
            //继续删除，但是每次删除都需要让sep的位置-1
            while(s[k]==' '){
                s.replace(k,1,"");
                index--;
            }
            //跳出这个循环的时候，代表碰到sep分隔符了,字符串已经处理完毕
            //cout <<"[while2]k:"<<k <<" str:"<< s << endl;
        }
        s.replace(index,1," ");
        s.erase(0,end_word);//删掉前面的原有单词
        s.erase(s.size()-1,1);//删除最后单词带的空格
        return s;
    }
};

结果 4MS 7MB

方案3

上面的办法看起来很对，实际上还是不是原地算法！

因为我每次都是在后面尾随字符串，而没有把原字符串删掉。如果源字符串很长，我这么做就相当于把源字符串的长度变为原有俩倍

  • 依旧是O(N)的空间复杂度

要想做到真原地，就需要在插入到指定位置的同时，将其原本的字符串给删除了

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//方案3
class Solution {
public:
    #define SEP '|'
    //从begin开始找到下一个空格的下标，不包括begin本身
    int find_space(string&s,int begin=0)
    {
        int i=0;
        for(i=begin+1;i<s.size();i++)
        {
            if(s[i]==' '){
                break;
            }
            else if(s[i]==SEP)
            {//用一个特殊字符作为原字符串结尾
                break;
            }
        }
        //如果是因为找到空格跳出，判断该字符串后面还有没有有效字符
        int k = i;//不能改i
        if(s[k]!=SEP)
        {
            while(s[k]==' ')
            {
                k++;
                //一直走到了|，代表没有有效字符了
                if(s[k]==SEP){
                    return s.npos;
                }
            }
            //走到这里代表有
            return i;
        }

        return s.npos;
    }

    string reverseWords(string s) {
        int i=0,end_word=0,index=0;
        int begin_sz = s.size();//起始大小
        s+=SEP;//用一个特殊字符作为原字符串结尾
        int sep_index = s.size()-1;//最后一个字符的位置就是分隔符
        
        for(i=0;i<begin_sz;i++)
        {
            // 跳过前导空格
            while(s[i]==' '){
                i++;
            }
            // 如果已经到最后面了，就直接跳出
            if(i>=begin_sz){
                break;
            }
            index = find_space(s,i);
            //如果找不到下一个空格了，代表当前是原字符串最后一个单词
            //跳过
            if(index == s.npos){
                end_word=i;
                break;
            }
            int sz = index-i;//单词长度
            string temp(s,i,sz);
            temp+=" ";
            //不能尾插，应该在sep之后插入
            //s += temp;
            s.insert(sep_index+1,temp);
            //printf("[%d-%d-1]%s\n",i,sep_index,s.c_str());

            // cout << i << " | " << index << " | "<< sz << endl;
            // cout << temp << "-" << endl;

            //构造了之后，把原str这部分删了(错误！删了之后下标变了，循环无意义)
            s.erase(i,sz);
            sep_index-=sz;
            //printf("[%d-%d-2]%s\n",i,sep_index,s.c_str());

            // i = i;//跳过当前单词
            //index-1是因为本次循环过了之后会被for给+1
        }
        //cout <<"[end]"<< s << endl;

        index = s.find(SEP);
        // 删除index之前,end_word之后的空格
        int k = s.find(" ",0);
        //cout << "k:" <<k<<" endw:" << end_word <<endl;
        while(k!=s.npos&&k<index){
            s.replace(k,1,"");
            index--;
            //cout <<"[while1]k:"<<k <<" str:"<< s << endl;
            //因为替换过了之后，k的位置变成了原有k的下一位
            //此时如果k还是空格，代表原字符串末尾有多个空格
            //继续删除，但是每次删除都需要让sep的位置-1
            while(s[k]==' '){
                s.replace(k,1,"");
                index--;
            }
            //跳出这个循环的时候，代表碰到sep分隔符了,字符串已经处理完毕
            //cout <<"[while2]k:"<<k <<" str:"<< s << endl;
            k = s.find(" ",0);
        }
        //cout <<"[end2]"<< s << endl;
        s[index]=' ';
        //s.erase(0,end_word);//删掉前面的原有单词
        s.erase(s.size()-1,1);//删除最后单词带的空格
        //cout <<"[return]"<< s << endl;
        return s;
    }
};

方案4，来自代码随想录P92

删除空格

这里对删除多余空格的代码做说明

1
_ _ a b c _ _ h e l l o _

对上述字符串而言，fast首先会走到第一个非空格的字符a，然后开始复写。

对于两个单词中的多余空格，fast会复制第一个给slow，并跳过剩余的空格。所以这里判断的是fast-1和fast位置相等且都是空格的时候才会跳过。

1
2
3
4
5
if(fast > 1 
	&& s[fast-1] == s[fast] 
	&& s[fast]==' '){
	continue;
}

对于末尾的空格而言，最后遍历的时候fast的位置如下时，它会将这个空格复制给slow的位置（因为判断多余空格是判断fast和fast-1元素相等的时候才认为是多余空格的）

1
2
3
4
5
6
0 1 2 3 4 5 6 7 8 9 0 1 2
_ _ a b c _ _ h e l l o _
						f
						
a b c _ h e l l o _ l o _ 
				  s 	f

复制完毕后，slow和fast都会加一，位置变化如下，fast指针越界退出循环，slow位置是在空格的下一位。

1
2
3
0 1 2 3 4 5 6 7 8 9 0 1 2
a b c _ h e l l o _ l o _ 
				    s 	  f

所以此时只需要判断slow-1的位置是不是空格，如果是空格，则新的字符串的大小是size-1，如果不是空格，那么slow就是新字符串的大小。

1
2
3
4
5
6
7
8
if(slow>1 && s[slow-1]==' ')
      {
          s.resize(slow-1);
      }
      else
      {
          s.resize(slow);
      }

完整代码

其他部分的代码说明详见注释

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//思路4，来自代码随想录P92
class Solution {
public:
    //删除空格，时间复杂度O(N)
    void removeSpace(string& s)
    {
        int slow=0,fast=0;
        //这个循环结束后，fast会走到第一个不为空格的字符上
        while(s.size()>0 && fast< s.size()&&s[fast]==' '){
            fast++;
        }
        //此时开始复写（也会将字符串开头的空格给替换掉）
        for(/*不写第一个，fast的位置没有变动*/;fast<s.size();fast++)
        {   
            //fast要大于1才能判断fast上一位
            //上一位和这一位不相等（判端连续空格）
            //当前位是否位空格（是就代表是连续空格）
            //continue会找到一段空格之后的第一个非空格字符
            if(fast > 1 
	            && s[fast-1] == s[fast]
                && s[fast]==' ')
                continue;
            else
            {//复写
                s[slow]=s[fast];
                slow++;
            }
        }
        // 复写结束后，此时slow所在位置是原有单词字符串的末尾，且可能会有一个多余的空格；
        // 在while循环中，fast指针会跳过多余空格，只复制一个空格给slow的位置
        // 这个操作是保证两个单词之间只有一个空格，所以slow此时顶多会是一个末尾的空格。
    
        // 只需要判断slow-1位置是不是空格，是的话，将其去掉就行
        // 注意，此时slow所在位置可能是源字符串中的字母上，并不一定是空格
        if(slow>1 && s[slow-1]==' ')
        {
            s.resize(slow-1);
        }
        else
        {
            s.resize(slow);
        }
    }
    
    //逆置字符串
    //每次逆置的时间复杂度为O((START-END)/2)
    void revserseString(string&s,int start,int end)
    {
        //等于的情况也是可以的，只不过此时压根不做交换
        assert(end<s.size()&&start<=end);
        int i=start,j=end;
        for(;i<j;i++,j--)
        {
            swap(s[i],s[j]);
        }
    }

    //思路有点类似`189轮转数组`中的三旋法
    //先去掉冗余空格
    //把整个字符串逆置
    //再单独逆置所有单词
    string reverseWords(string s) {
        //删多余空格
        removeSpace(s);
        //逆置字符串
        revserseString(s,0,s.size()-1);
        //printf("|%s|\n",s.c_str());
        //扫描出单词，逆置每个单词
        //因为已经删除多余空格了，所以s[0]肯定是单词
        int begin=0,cur=1;
        while(cur<s.size() && begin<s.size())
        {
            //当前不是空格++
            while(cur!=begin&&s[cur]!=' '&&cur<s.size())
            {
                //cout << begin << "-" << cur<< "-" << s[cur]<<endl;
                cur++;
            }
            //停下来代表是空格,逆置
            //如果是最后一个单词，停下来的时候是因为cur==s.size()
            //此时cur-1就正好是倒数第一个字符
            //cout << begin << " " << cur <<endl;
            revserseString(s,begin,cur-1);
            //更新下标
            begin= cur+1;
            cur+=2;//保证cur是begin的下一位
        }
        return s;
    }
};

测试 4MS 6.8MB

一定要记得删除printf

以后写oj的时候，一定要记得删除用来debug的printf，否则用时特别特别长！

如下相同代码，删除pirntf之后快了十倍

image-20230427180614095