[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 如下

	class Solution {
	public:
	void reverseWords(string &s) {
	if(s.empty()) {
	return;
	}
	int left;
	for(int i = 0; i < s.length(); i++) {
	if(s[i] == ' ') {
	//> remove leading space
	s.erase(i, 1);
	--i;
	}
	else {
	//> find a word
	left = i;
	++i;
	while(i < s.length() && s[i] != ' ') {
	++i;
	}
	//> reverse the word, but single char no need to reverse
	if((i - left) > 1) {
	reverseWord(s, left, i-1);
	}
	}
	}
	//> remove trailing space
	int right = s.length() - 1;
	while(s[right] == ' ' ) {
	--right;
	}
	s.erase(right+1, s.length() - right);
	//> remove entire string
	reverseWord(s, 0, s.length()-1);
	}
	void reverseWord(string &s, int left, int right) {
	while(left < right) {
	swap(s[left++], s[right--]);
	}
	}
	};

view raw reverseWordsInString_1.cpp hosted with ❤ by GitHub

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

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

所以解題想法變如下

• 用 s 創一個 istringstream

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

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

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

code 如下

	class Solution {
	public:
	void reverseWords(string &s) {
	istringstream iss(s);
	//> iss will skip all the spaces
	//> use s to hold the first word
	iss >> s; //> s now equal the first word
	//> put remaining words into s in reverse order
	string tmp;
	while(iss >> tmp) {
	s = tmp + " " + s;
	}
	//> one thing need to notice
	//> if s only contains spaces
	//> then iss will output empty string ""
	//> need to check this
	if(s[0] == ' ') {
	s = "";
	}
	}
	};

view raw reverseWordsInString_2.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public String reverseWords(String s) {
	String[] words = s.split(" ");
	int index = words.length - 1;
	StringBuilder sb = new StringBuilder();
	while(index >= 0) {
	if(!words[index].isEmpty()) {
	sb.append(words[index]).append(" ");
	}
	index--;
	}
	return sb.toString().trim();
	}
	}

view raw reverseWords.java hosted with ❤ by GitHub