Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
并remove extra spaces

Solution1：按char操作

思路： 整体全部chars reverse + every words reverse
Time Complexity: O(N) Space Complexity: O(N) 算返回的result

Solution2：按word操作，逆序输出

思路：按word操作，逆序输出
Time Complexity: O(N) Space Complexity: O(N) 算返回的result

Solution1 Code：

public class Solution {
  
    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;
        }
    }
}

Solution2 Code：

public class Solution2 {
    public String reverseWords(String s) {        
        String[] tmp = s.split("\\s");
        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= tmp.length; i++){
            if(tmp[tmp.length - i].equals("")){
                continue;
            }

            sb.append(tmp[tmp.length - i]);
            sb.append(" ");
        }

        return sb.toString().trim();
    }
}

or

public class Solution2 {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}