LeetCode 151. Reverse Words in a String

题目

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.

思路

一！定！要！考！虑！各！种！情！况！比如

" "//一个空格
"   What am   I doing     "

然后这种倒转问题的原地处理思路应该都明白的，先把整个字符串倒转一遍，然后按照单词再倒转回来，拿”the sky is blue”为例：

1. “eulb si yks eht“
2. “blue si yks eht”
3. “blue is yks eht”
4. …
5. “blue is sky the”

代码

class Solution {
public:
	void reverseWordsSub(string &s, int start, int end) {
		//[start,end]
		char c;
		int count = 0;
		const int maxInd = (end - start - 1) / 2 + start;
		for (int i = start; i <= maxInd; i++) {
			c = s[i];
			s[i] = s[end - count];
			s[end - count] = c;
			count++;
		}
	}
	void clearStr(string &s) {
		//Clear unnecessary spaces
		int validIndex = -1;
		bool spaceFlag = false;
		for (int i = 0; i<s.size(); i++) {
			if (s[i] != ' ') {
				s[++validIndex] = s[i];
				spaceFlag = false;
			}
			else if (!spaceFlag) {
				if (validIndex < 0) {
					continue;
				}
				spaceFlag = true;
				s[++validIndex] = s[i];
			}
		}
		if (spaceFlag)
			validIndex--;
		if (validIndex < 0)
			s = "";
		else
			s = s.substr(0, validIndex + 1);
	}
	void reverseWords(string &s) {
		clearStr(s);
		int strSz = s.size();
		reverseWordsSub(s, 0, strSz - 1);
		int start = 0;
		for (int i = 0; i<strSz; i++) {
			if (s[i] == ' ') {
				reverseWordsSub(s, start, i - 1);
				start = i + 1;
			}
		}
		reverseWordsSub(s, start, strSz - 1);
	}
};