反转 单词 （单词 反转）

给定一个字符串，其中单词之间以空格进行分隔，现在要求将整个字符串的单词进行反转。

输入

“this is a sentence”

输出

sentence a is this

首先，题目要求把每个单词倒过来，同时联想到栈有先进先出的特点。如果我们把单词作为一个整体按顺序入栈，然后再全部出栈，这时得到的就是反转后的句子了。

#include
#include
#include

using namespace std;

int main() {
	string str;
	getline(cin, str);

	stack wordStack;
	int len = str.size();
	string temp="";
	for (int i = 0; i < len; i++) {
		if (str[i] != ' ') {
			temp += str[i];
		}
		else {
			wordStack.push(temp);
			temp.clear();
		}
	}
	wordStack.push(temp);
	string tempword;
	while (!wordStack.empty())
	{
		tempword = wordStack.top();
		wordStack.pop();
		if (!wordStack.empty()) {
			cout << tempword << ' ';
		}
		else
		{
			cout << tempword;
		}
	}
	return 0;
}

时间复杂度：遍历一遍数组+输出所有单词。时间复杂度为 O ( n ) O(n) O(n)

空间复杂度： O ( n ) O(n) O(n)因需要额外的栈存放所有的单词。

可能一下想不到很好的方法来解决空间问题。不妨先考虑一个简单的问题。用常数空间复杂度将整个字符串反转这一点是很容易做到的（使用双指针不断交换两个字符就可以了）。当把整个字符串反转以后原来的句子会是什么样子呢？

可以看出，在整个字符串反转后，可以看到单词的相对位置就已经反转过来了，但是对于每个单词依然内部字母是反转的，因此考虑是否有方法将每个单词进行反转，这样单词字母的顺序就变过来了。

没错，把每个单词作为一个独立的字符串进行反转就可以了。

#include
#include
#include

using namespace std;
void reverseStr(string& str, int beg, int end) {
	while (beg < end) {
		swap(str[beg++], str[end--]);
	}
}
int main() {
	string str;
	getline(cin, str);
	reverseStr(str, 0, str.size() - 1);
	int begin=0, end=0;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] != ' ') {
			end=i;
		}
		else {
			reverseStr(str, begin, end);
			begin = end + 2;
		}
	}
	reverseStr(str, begin, end);
	cout << str;
	return 0;
}

其实像对于反转这类题目，或者说要改变原来的线性结构的顺序的问题，多次反转是一个比较常见的思路。和本题比较类似的是数组的循环左移，这个题也是利用多次逆转改变数字的相对顺序。进一步拓展，如果将问题修改为将一个字符串前n个单词左移的话是否可以用 O ( 1 ) O(1) O(1)的空间复杂度解决？

更多问题请访问   知乎：https://www.zhihu.com/people/stark-33-42
CSDN：https://blog.csdn.net/issc2?spm=1011.2124.3001.5343