151 Reverse Words in a String 翻轉(zhuǎn)字符串里的單詞

Description:
Given an input string, reverse the string word by word.

Example:

Example 1:

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

Example 2:

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

Example 3:

Input: "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.

Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

題目描述:
給定一個(gè)字符串，逐個(gè)翻轉(zhuǎn)字符串中的每個(gè)單詞。

示例 :

示例 1：

輸入: "the sky is blue"
輸出: "blue is sky the"

示例 2：

輸入: " hello world! "
輸出: "world! hello"
解釋: 輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。

示例 3：

輸入: "a good example"
輸出: "example good a"
解釋: 如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。

說(shuō)明：

無(wú)空格字符構(gòu)成一個(gè)單詞。
輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。
如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。

進(jìn)階：

請(qǐng)選用 C 語(yǔ)言的用戶(hù)嘗試使用 O(1) 額外空間復(fù)雜度的原地解法。

思路:

參考LeetCode #189 Rotate Array 旋轉(zhuǎn)數(shù)組
先將整個(gè)字符串反轉(zhuǎn)
再按空格反轉(zhuǎn)每個(gè)單詞并去掉額外的空格
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    string reverseWords(string s) 
    {
        stringstream ss;
        string result = "", temp;
        ss << s;
        while (ss >> temp) result = " " + temp + result;
        if (result.size()) result.erase(result.begin());
        return result;
    }
};

Java:

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}

Python:

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))