翻转字符串里的单词

翻转字符串里的单词

题目：

给定一个字符串，逐个翻转字符串中的每个单词。
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
你可以按 任意顺序 返回答案 。
示例 1：

  • 输入：” the sky is blue “
  • 输出：”blue is sky the”
    示例 2：
  • 输入：” hello world! “
  • 输出：”world! hello”
    示例 3：
  • 输入: “a good example”
  • 输出: “example good a”
  • 力扣题目链接

解法-双指针法

思路：以" the sky is blue "为例

  1. 移除多余空格"the sky is blue"
  2. 反转整个字符串"eulb si yks eht"
  3. 将每个单词反转"blue is sky the"

复杂度：

  • 时间复杂度：
  • 空间复杂度：

代码：

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
class Solution {
public:
    //反转,闭区间
    void reverse(string& s,int start,int end)
    {
        int slow = start,fast = end;
        while(slow < fast)
        {
            swap(s[slow++],s[fast--]);
        }
    }
    //去除多余空格
    void removeExtraSpaces(string& s)
    {
        //去除首空格
        int slow = 0,fast = 0;
        while(s[fast] == ' ')
        {
            fast++;
        }
        //去除中间空格
        for(;fast < s.size();fast++)
        {
            if(s[fast] == ' ' && s[fast-1] == s[fast])
            {//说明此处是多余空格，跳过,fast++
                continue;
            }else{
                s[slow]=s[fast];
                slow++;
            }
        }
        //去除尾空格,因为去除中间空格时，可能会出现最后一个字符是空格的情况
        if(s[slow-1] == ' ')
        {
            s.resize(slow-1);
        }else{//更新新的字符串长度
            s.resize(slow);
        }
    }
    //反转字符串里的单词
    string reverseWords(string s)
    {
        //去除多余空格
        removeExtraSpaces(s);
        // //反转整个字符串,反转后的字符串首尾都是字母
        reverse(s,0,s.size()-1);
        //将每个单词反转
        int begin = 0;
        for(int i = 0;i<s.size();++i)
        {
            if(s[i] == ' ')
            {
                reverse(s,begin,i-1);
                begin = i+1;
            }
        }
        //单独处理最后一个字母
        reverse(s,begin,s.size()-1);
        return s;
    }

};

语法小计

  1. 该题没语法小计
    *
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。