刷题

翻转单词顺序

scorlw 发布于

翻转单词顺序

关键词：双指针、string

题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例 1：

1
2
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

1
2
3
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例3：

1
2
3
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解法

解法一：

思路：

  • 双指针的思想，利用双指针指向每个单词的头和尾，使用substr函数添加到ans

算法流程：

  1. 从后往前遍历数组；
  2. 遇到不是空格，记录单词长度；
  3. 使用substr将单词添加到ans；
  4. 考虑第一个单词；
  5. 删除多余空格。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string reverseWords(string s) {
        if(s.empty())return s;
        int len = 0;
        string ans = "";
        for(int m = s.size()-1; m >=0; m--)//遍历
        {
            if(s[m]==' '&&len!=0)//一个单词结束
            {
                ans += s.substr(m+1,len)+ " ";len = 0; continue;//ans添加从m+!到len的s
            }
            if(s[m]!= ' ')len++;//使用len记录单词长度
        }
        if(len !=0) ans += s.substr(0,len) + " ";//添加s的第一个单词（如果有）
        if(ans.size()>0) ans.erase(ans.size()-1,1);//删除最后加上去的空格
        return ans;
    }
};

知识点

  1. 双指针；
  2. substr函数（string的用法）