题目描述

题目链接：151. Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

例子

例子 1

Input: s = "the sky is blue" Output: blue is sky the

例子 2

Input: s = " hello world " Output: world hello Explanation: Your reversed string should not contain leading or trailing spaces.

例子 3

Input: s = "a good example" Output: example good a Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints

• 1 <= s.length <= 104
• s contains English letters (upper-case and lower-case), digits, and spaces ' '
• There is at least one word in s

Follow Up

If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

解题思路

这道题要求反转一个字符串中单词的顺序，并且过滤掉多余的空格。如果不要求 in-place 的话只需要用双指针的方法筛选出每个单词再按照相反顺序用一个空格连接起来即可。要求 in-place 的情况也不是特别复杂，基本思路如下：

• 过滤空格，这个过程可以用双指针实现，具体见代码。多余的空间需要 pop-back 掉
• 反转整个字符串，单词本身也会被反转
• 用双指针搜索每个单词的起始和结束位置，再进行一次反转即可

代码如下所示：

#include<string>
#include<algorithm>

class Solution {
public:
    std::string reverseWords(std::string s) {
        int back = 0;
        int front = 0;

        // filter spaces
        while (front < s.length())
        {
            while (front < s.length() && s[front] == ' ') front++;

            if (front == s.length()) break;

            if (back != 0){
                s[back] = ' ';
                back++;
            }
            
            while (front < s.length() && s[front] != ' ')
            {
                s[back] = s[front];
                back++;
                front++;
            }
        }
        
        // remove extra space
        while(back < front) {
            s.pop_back();
            front--;
        }
        
        // reverse whole string, words would be reversed as well
        std::reverse(s.begin(), s.end());
        back = 0;
        front = 0;

        // for each word, reverse it back to normal order
        while (front < s.length())
        {
            while (front < s.length() && s[front] != ' ')
            {
                front++;
            }
            std::reverse(s.begin() + back, s.begin() + front);
            back = front + 1;
            front = back;
        }

        return s;
    }

};

• 时间复杂度: O(N) – 第一次过滤遍历一次，整体反转遍历一次，对每个单词搜索并反转相当于遍历两次
• 空间复杂度: O(1)

GitHub 代码同步地址： 151.ReverseWordsInAString.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions