[LeetCode] Reverse Words in a String 翻轉字元串中的單詞

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

For example,

Given s = "<code>the sky is blue</code>",

return "<code>blue is sky the</code>".

Update (2015-02-12):

For C programmers: Try to solve it in-place in O(1) space.

<a href="https://leetcode.com/problems/reverse-words-in-a-string/">click to show clarification.</a>

Clarification:

What constitutes a word?

A sequence of non-space characters constitutes a word.

Could the input string contain leading or trailing spaces?

Yes. However, your reversed string should not contain leading or trailing spaces.

How about multiple spaces between two words?

Reduce them to a single space in the reversed string.

這道題讓我們翻轉字元串中的單詞，題目中給了我們寫特别說明，如果單詞之間遇到多個空格，隻能傳回一個，而且首尾不能有單詞，并且對C語言程式員要求空間複雜度為O(1)，是以我們隻能對原字元串s之間做修改，而不能聲明新的字元串。那麼我們如何翻轉字元串中的單詞呢，我們的做法是，先整個字元串整體翻轉一次，然後再分别翻轉每一個單詞（或者先分别翻轉每一個單詞，然後再整個字元串整體翻轉一次），此時就能得到我們需要的結果了。那麼這裡我們需要定義一些變量來輔助我們解題，storeIndex表示目前存儲到的位置，n為字元串的長度。我們先給整個字元串反轉一下，然後我們開始循環，遇到空格直接跳過，如果是非空格字元，我們此時看storeIndex是否為0，為0的話表示第一個單詞，不用增加空格；如果不為0，說明不是第一個單詞，需要在單詞中間加一個空格，然後我們要找到下一個單詞的結束位置我們用一個while循環來找下一個為空格的位置，在此過程中繼續覆寫原字元串，找到結束位置了，下面就來翻轉這個單詞，然後更新i為結尾位置，最後周遊結束，我們剪裁原字元串到storeIndex位置，就可以得到我們需要的結果，代碼如下：

C++ 解法一：

Java解法一：

下面我們來看使用字元串流類stringstream的解法，我們先把字元串裝載入字元串流中，然後定義一個臨時變量tmp，然後把第一個單詞賦給s，這裡需要注意的是，如果含有非空格字元，那麼每次&gt;&gt;操作就會提取連在一起的非空格字元，那麼我們每次将其加在s前面即可；如果原字元串為空，那麼就不會進入while循環；如果原字元串為許多空格字元連在一起，那麼第一個&gt;&gt;操作就會提取出這些空格字元放入s中，然後不進入while循環，這時候我們隻要判斷一下s的首字元是否為空格字元，是的話就将s清空即可，參見代碼如下：

C++ 解法二：

下面這種方法也是使用stringstream來做，但是我們使用了getline來做，第三個參數是設定分隔字元，我們用空格字元來分隔，這個跟上面的&gt;&gt;操作是有不同的，每次隻能過一個空格字元，如果有多個空格字元連在一起，那麼t會指派為空字元串，是以我們在處理t的時候首先要判斷其是否為空，是的話直接跳過，參見代碼如下：

C++ 解法三：

而如果我們使用Java的String的split函數來做的話就非常簡單了，沒有那麼多的幺蛾子，簡單明了，我們首先将原字元串調用trim()來去除備援空格，然後調用split()來分隔，分隔符設為"\\s+"，這其實是一個正規表達式，\\s表示空格字元，+表示可以有一個或多個空格字元，那麼我們就可以把單詞分隔開裝入一個字元串數組中，然後我們從末尾開始，一個個把單詞取出來加入結果res中，并且單詞之間加上空格字元，注意我們把第一個單詞留着不取，然後傳回的時候再加上即可，參見代碼如下：

Java解法二：

下面這種方法就更加的簡單了，瘋狂的利用到了Java的内置函數，這也是Java的強大之處，注意這裡的分隔符沒有用正規表達式，而是直接放了個空格符進去，後面還是有+号，跟上面的寫法得到的效果是一樣的，然後我們對字元串數組進行翻轉，然後調用join()函數來把字元串數組拼接成一個字元串，中間夾上空格符即可，參見代碼如下：

Java解法三：