LeetCode151. 反轉字元串中的單詞

拿到這道題，我們想一下，我們將整個字元串都反轉過來，那麼單詞的順序指定是倒序了，只不過單詞本身也倒序了，那麼再把單詞反轉一下，單詞不就正過來了。

所以解題思路如下：

移除多餘空格

將整個字元串反轉

將每個單詞反轉

舉個例子，源字元串為："the sky is blue "

移除多餘空格 : "the sky is blue"

字元串反轉："eulb si yks eht"

單詞反轉："blue is sky the"

這樣我們就完成了翻轉字元串里的單詞。

那麼現在的思路就非常清晰明瞭了，先將整個字元串進行反轉，再去除多餘的空格，最後將每個單詞進行反轉

以下我對最難的部分---移除多餘的空格進行講解：

我們可以採用雙指針的思想進行移除多餘空格的操作，快指針用來遍歷我們的數組，慢指針用於更新我們需要保留的元素的索引

不過有一個邏輯需要特別處理一下，就是要在每個單詞之間加上空格（首單詞除外）——判斷邏輯可以表示為

if(slow!=0) s[slow++]=' ';

這樣就可以做到在每個單詞之間加上空格，並且去除首字母前面的空格了。

具體函數實現的代碼如下：

	//去除字元串中多餘的空格
	void removeExtraSpaces(string& s)
	{
		int fast = 0, slow = 0;
		for (fast = 0; fast < s.size(); fast++) {
			//快指針指向我們要保留的字元
			if (s[fast] != ' ') {
				//將每個單詞之間加上空格，首單詞除外
				if (slow != 0) s[slow++] = ' ';
				//將單詞中間的空格去除
				while (fast < s.size() && s[fast] != ' ') {
					s[slow++] = s[fast++];
				}
			}
		}
		s.resize(slow);
	}

其餘兩個步驟的代碼比較簡單，我在這裡就不過多贅述了

具體可以編譯運行的代碼如下：

class Solution {
public:
	//反轉字元串中的某段
	void reverse(string& s, int start, int end)
	{
		for (int i = start, j = end; i < j; i++, j--) {
			swap(s[i], s[j]);
		}
	}
	//去除字元串中多餘的空格
	void removeExtraSpaces(string& s)
	{
		int fast = 0, slow = 0;
		for (fast = 0; fast < s.size(); fast++) {
			//快指針指向我們要保留的字元
			if (s[fast] != ' ') {
				//將每個單詞之間加上空格，首單詞除外
				if (slow != 0) s[slow++] = ' ';
				//將單詞中間的空格去除
				while (fast < s.size() && s[fast] != ' ') {
					s[slow++] = s[fast++];
				}
			}
		}
		s.resize(slow);
	}
	string reverseWords(string& s)
	{
		//移除字元串中多餘的空格
		removeExtraSpaces(s);
		//反轉這個字元串
		reverse(s, 0, s.size() - 1);
		//反轉這個字元串中的每一個單詞
		int start = 0;
		for (int i = 0; i <= s.size(); i++) {
			if ( i == s.size()||s[i]==' ') {
				reverse(s, start, i - 1);
				start = i + 1;
			}
		}
		return s;
	}
};