151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

无空格字符构成一个 单词 。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例 1：

输入：“the sky is blue”
输出：“blue is sky the”
示例 2：

输入：" hello world! "
输出：“world! hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入：“a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路：

开辟一个和原字符串大小相同的数组用来存储翻转后字符串。

从原字符串尾部开始向前寻找，查找到一个单词后放入新数组。

这种解法需要 O(N) 的空间复杂度。

代码示例：

char* reverseWords(char* s)
{
	int len = strlen(s);
	//新数组
	char* newArr = (char*)malloc(sizeof(char) * len + 1);

	int prev = len - 1; //每个单词的头 
	int tail = prev; //每个单词的尾 
	int cur = 0; //临时记录
	int index = 0; //新数组的索引

	while (prev >= 0) //小于0停止拷贝
	{
		if (s[prev] == ' ') //遇到非空格停止，找到单词尾部
		{
			prev--;
		}
		else
		{
			tail = prev; //记录尾部
			while (prev >= 0 && s[prev] != ' ') //移动，寻找头部 注意prev越界
			{
				prev--;
			}

			cur = prev + 1; //prev此时指向' '，+1让cur指向单词头字母
			while (cur <= tail)
			{
				newArr[index++] = s[cur++]; //复制单词
			}

			newArr[index++] = ' '; //在每个单词后添加' '
		}

	}

	if (index > 0 && newArr[index - 1] == ' ') //注意补上字符串的结尾 \0
	{
		newArr[index - 1] = 0;
	}
	else //这是全是空格的情况  
	{
		newArr[index] = 0;
	}

	return newArr;
}