题目描述（中等难度）

将字符串的每个单词反过来，单词内部不需要逆转，注意可能会有多余的空格。

解法一

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

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

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

public String reverseWords(String s) { Stack<String> 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 it in-place in O(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 string reverse(a, 0, n - 1); // step 2. reverse each word reverseWords(a, n); // step 3. clean up spaces return 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 spaces while (j < i || j < n && a[j] != ' ') j++; // skip non spaces reverse(a, i, j - 1); // reverse the word } } // trim leading, trailing and multiple spaces String cleanSpaces(char[] a, int n) { int i = 0, j = 0; while (j < n) { while (j < n && a[j] == ' ') j++; // skip spaces while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces while (j < n && a[j] == ' ') j++; // skip spaces if (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; } } 

总

一开始没有 get 到题目要求空间复杂度为 O(1) 的想法，后来在 discuss 中才突然明白。