[LeetCode] 151. Reverse Words in a String

轉自LeetCode

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

For example,
Given s = "the sky is blue",
return "blue is sky the".

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

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.

<Solution>

這題比較麻煩的地方是 clarification 的部分

• 第一點沒問題，就是用空白來區隔 word

• 第二點是要去處理 input 有 leading or trailing spaces 的狀況，且最後的答案不能有

• 第三點是在說，在最後的答案裡，word之間只能有一個空白，不管它們在 input的時候，有多少空白來間隔

所以在寫的時候，要注意上面的三種條件

那一開始先看怎麼反轉 string，以 the sky is blue為例

首先，先反轉每個 word : eht yks si eulb

然後，再反轉整個 string : blue is sky the，這樣就大功告成

那如何解題，首先歷遍 string，過程中

• 遇到 leading spaces，刪除

• 遇到字元，找出整個 word ，然後反轉 word

這邊要注意第二個步驟，當 input 有 trailing spaces 時會有問題

用 s = "-a--bc--" 舉例，- 代表空白

• s[0] = '-' : leading space，刪除

• s[0] = 'a' : 因為上一步驟是刪除，所以 index 還是在 0。發現字元，移動 index 找出整個 word
• index 移動到 1 停 : s[0] = 'a', s[1] = '-'，找到 word，reverse s[0] 到 s[0]

• s[2] = '-' : 繼續歷遍，index+1 = 2，這時候是空白，leading space，刪除

• s[2] = 'b' : 上一步驟是刪除，所以 index 還是在 2。發現字元，移動 index 找出整個 word
• index 移動到 4 停 : s[2] = 'b',s[3] = 'c', s[4] = '-'，找到 word，reverse s[2] 到 s[3]

• s[5] = '-' : 繼續歷遍，index+1 = 5，這時候是空白，leading space，刪除

最後 s = "a-bc-"

因為題目要求每個 word 之間用一個空白間隔，所以在步驟2都會留一個空白下來

但在最後一個 word 的時候，就會留下 trailing spaces

所以歷遍完之後，要再把 trailing spaces 拿掉

code 如下

那如果不想自己處理空白的問題，可以使用 istringstream

istringstream 它會忽略所有的空白，直接給你 word

所以解題想法變如下

• 用 s 創一個 istringstream

• 利用 istringstream 來切出每個 word，並且用 reverse order 的方式接起來

那使用 istringstream 要注意一點是，如果 s 只有空白沒有字元

那麼 istregstream 會輸出空字串，這個部分要特別處理

code 如下


Java