Reverse the words in a sentence and truncate all heading/trailing/duplicate space characters.

Examples

• “ I love Google ” → “Google love I”

Corner Cases

• If the given string is null, we do not need to do anything.

Solution: 第一步，先去除多余空格（除第一个单词外，每个单词前有一空格）。第二步，整体翻转。第三步，翻转每个单词。

  public String reverseWords(String input) {
    if (input == null || input.length() == 0) {
      return input;
    }
    char[] chars = input.toCharArray();
    int j = 0;
    while (j < chars.length && chars[j] == ' ') {
      j++;
    }
    int i = 0;
    while (j < chars.length) {
      if (chars[j] != ' ' || chars[j] == ' ' && j + 1 < chars.length && chars[j + 1] != ' ') {
        chars[i++] = chars[j];
      }
      j++;
    }
    if (i == 0) {
      return "";
    }
    reverse(chars, 0, i - 1);
    int start = -1, end = -1;
    for (int k = 0; k < i; k++) {
      if (k == 0 || chars[k - 1] == ' ') {
        start = k;
      }
      if (k == i - 1 || chars[k + 1] == ' ') {
        end = k;
      }
      if (start != -1 && end != -1) {
        reverse(chars, start, end);
        start = -1;
        end = -1;
      }
    }
    return new String(chars, 0, i);
  }
  private void reverse(char[] a, int i, int j) {
    while (i < j) {
      char temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      i++;
      j--;
    }
  }