P136 翻转单词顺序

描述#

这个题目说的是，给你一个英文句子，你要翻转句子中单词的顺序。注意，句子中的标点视为单词的一部分。原始句子的开头和结尾可能包含多余的空格，并且相邻单词之间也可能有多个空格。在翻转单词顺序后，句子的开头和结尾不能包含多余的空格，并且相邻单词之间也只允许有一个空格。

比如说，给你的句子是：
"  hi, how  are you?  "
这个句子的开头和结尾都有两个多余的空格，并且 how 和 are 之间也是两个空格。
把这几个单词翻转顺序后，得到：
"you? are how hi,"
可以看到，翻转单词后的句子开头和结尾都不包含多余的空格，并且相邻单词之间只有一个空格。另外，标点符号也跟着邻接的单词一起移动。

代码#

public class AlgoCasts {

  private void reverse(char[] str, int i, int j) {
    for (; i < j; ++i, --j) {
      char tmp = str[i];
      str[i] = str[j];
      str[j] = tmp;
    }
  }

  // Time: O(n), Space: O(n)
  public String reverseWords(String s) {
    if (s == null || s.length() == 0) return s;
    char[] str = s.toCharArray();
    int p = 0, q = 0, end = str.length - 1;
    while (end >= 0 && str[end] == ' ') --end;
    while (q <= end) {
      // the start position of a word
      int start = p;
      // skip spaces
      while (q <= end && str[q] == ' ') ++q;
      // copy a word
      while (q <= end && str[q] != ' ') str[p++] = str[q++];
      // reverse the word
      reverse(str, start, p-1);
      // make a space
      if (q <= end) str[p++] = ' ';
    }
    // reverse the whole string, 0 ~ p-1
    reverse(str, 0, p-1);
    return new String(str, 0, p);
  }

}