给你一个字符串s，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"输出："blue is sky the"

示例 2：

输入：s = " hello world "输出："world hello"解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a goodexample"输出："example good a"解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

解法一

题目很直观，做法也会很直观，哈哈。遍历原字符串，遇到字母就加到一个temp变量中，遇到空格，如果temp变量不为空，就把temp组成的单词加到一个栈中，然后清空temp继续遍历。

最后，将栈中的每个单词依次拿出来拼接即可。

有一个技巧可以用，就是最后一个单词后边可能没有空格，为了统一，我们可以人为的在字符串后边加入一个空格。

public String reverseWords(String s) {Stack stack = new Stack();StringBuilder temp = new StringBuilder();s += " ";for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == ' ') {if (temp.length() != 0) {stack.push(temp.toString());temp = new StringBuilder();}} else {temp.append(s.charAt(i));}}if (stack.isEmpty()) {return "";}StringBuilder res = new StringBuilder();res.append(stack.pop());while (!stack.isEmpty()) {res.append(" ");res.append(stack.pop());}return res.toString();}

解法二

可以看下题目中的Follow up。

For C programmers, try to solve itin-placeinO(1) extra space.

如果用 C 语言，试着不用额外空间解决这个问题。

我们一直用的是 java，而 java 中的String变量是不可更改的，如果对它修改其实又会去重新创建新的内存空间。

而 C 语言不同，C 语言中的string本质上其实是char数组，所以我们可以在给定的string上直接进行修改而不使用额外空间。

为了曲线救国，继续用 java 实现，我们先将String转为char数组，所有的操作都在char数组上进行。

 char[] a = s.toCharArray();

至于算法的话，参考了这里-no-split(-)-no-StringBuilder)。

主要是三个步骤即可。

  1. 原地逆转char数组，这会导致每个单词内部也被逆转，接下来进行第二步
  2. 原地逆转每个单词
  3. 去除多余的空格

具体代码的话就直接从这里-no-split(-)-no-StringBuilder) 粘贴过来了，写的很简洁。几个封装的函数，关键就是去解决怎么原地完成。

public String reverseWords(String s) {if (s == null) return null;char[] a = s.toCharArray();int n = a.length;// step 1. reverse the whole stringreverse(a, 0, n - 1);// step 2. reverse each wordreverseWords(a, n);// step 3. clean up spacesreturn cleanSpaces(a, n);}void reverseWords(char[] a, int n) {int i = 0, j = 0;while (i < n) {while (i < j || i < n && a[i] == ' ') i++; // skip spaceswhile (j < i || j < n && a[j] != ' ') j++; // skip non spacesreverse(a, i, j - 1);// reverse the word}}// trim leading, trailing and multiple spacesString cleanSpaces(char[] a, int n) {int i = 0, j = 0;while (j < n) {while (j < n && a[j] == ' ') j++; // skip spaceswhile (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaceswhile (j < n && a[j] == ' ') j++; // skip spacesif (j < n) a[i++] = ' ';// keep only one space}return new String(a).substring(0, i);}// reverse a[] from a[i] to a[j]private void reverse(char[] a, int i, int j) {while (i < j) {char t = a[i];a[i++] = a[j];a[j--] = t;}}