151. Reverse Words in a String

本题其实不难，不过如果考虑到Follow Up中对C语言 的空间复杂度要求，就稍微有一点难度，不过其实也就是一道普通的medium题，本题令人困惑的点是到底什么built-in function是可以用的，什么built-in function是不能用的。

不过为了尽可能贴近题意，我还是用了类似C语言空间复杂度的解法，虽然对于我用的Java来说，由于要使用String，所以不存在的空间复杂度，但是解法还是尽量往那边靠

步骤：

1. 把String 转化成 Char Array
2. reverse整个array
3. 用遍历，对每个word进行reverse操作
4. 进行space的合并和清理

本题的难度在于细节，而即便细节也不算太复杂，我看完答案后第一遍就通过了，所以其实还好
代码如下:

class Solution {
  public String reverseWords(String s) {
    if (s == null || s.isEmpty()) {
      return s;
    }
    char[] sArr = s.toCharArray();
    reverse(sArr, 0, sArr.length - 1);
    reverseEachWord(sArr);
    return cleanSpace(sArr);
  }
  private String cleanSpace(char[] str) {
    int i = 0;
    int j = 0;
    while (j < str.length) {
      if (str[j] == ' ') {
        ++j;
        continue;
      }
      if (i > 0) {
        str[i++] = ' '; // if not beginning, append space before the word
      }
      while (j < str.length && str[j] != ' ') {
        str[i++] = str[j++];
      }
    }
    return String.valueOf(str).substring(0, i);
  }
  private void reverseEachWord(char[] str) {
    int i = 0;
    while (i < str.length) {
      if (str[i] == ' ') {
        ++i;
        continue;
      }
      int j = i + 1;
      while (j < str.length && str[j] != ' ') {
        ++j;
      }
      reverse(str, i, j - 1);
      i = j + 1;
    }
  }
  private void reverse(char[] str, int i, int j) {
    while (i < j) {
      char tmp = str[i];
      str[i] = str[j];
      str[j] = tmp;
      ++i;
      --j;
    }
  }
}