Title Description

Give you a string s and flip all the words in the string one by one.
A word is a string of non whitespace characters. Use at least one space in s to separate words in the string.
Please return a string that flips the word order in s and connects it with a single space.
explain:
The input string s can contain extra spaces before, after, or between words.
After flipping, the words should be separated by only one space.
The flipped string should not contain additional spaces.

Example description

Example 1:

Input: s = "the sky is blue"
Output:"blue is sky the"
Example 2:

Input: s = "  hello world  "
Output:"world hello"
Explanation: the input string can contain extra spaces before or after, but the flipped characters cannot be included.

thinking

Common handling of strings
Method 1: flip twice

1. Difficulty: flip the word as the smallest unit. This difficulty is divided into two steps as follows,
   The first step is to flip the whole string in characters.
   Step 2, flip each word.
   The above two steps can be interchanged and equivalent (as can be seen by drawing)
   
2. Delete spaces, enumerate valid spaces from front to back, put valid characters at the front of the array, search for a word every time, and remember to fill in a space after moving
   
   Method 2: double pointer + one-time traversal to realize flipping
   The idea of this method is jumping and does not need to really realize "flipping". The details are as follows:
3. Because you want to reverse the words in the character, you can traverse from back to front with double pointers (pointing to the left and right boundaries), constantly look for words, then add them to the result set, and add a separated space at the same time. Loop until all are found or the boundary is out of bounds. Finally, delete the extra space after the last word. (it's a little tricky... But it's really awesome)
4. Key: the whole process is processed from back to front, and the words are directly intercepted

The above two methods both involve StringBuffer and many common functions for string processing

code

Method 1:

class Solution {
    public String reverseWords(String s) {
       StringBuffer sb = new StringBuffer(s);
       int n = s.length();
       //Subscript used to index valid characters
       int k = 0;
       for (int i = 0; i < n; i ++ ) {
           //Filter invalid spaces
           if (sb.charAt(i) == ' ') continue;
           //First, flip each word
           int j = i, t = k; //t record the first character of the word
           //j to determine the subscript range of the word, and k to find the characters at the end of the word
           while (j < n && sb.charAt(j) != ' ') sb.setCharAt(k ++, sb.charAt(j ++ ));
           //Flip Words 
           reverse(sb, t, k - 1);
           //Add a space separation. Pay attention to whether it exceeds the boundary and cannot be filled
           if (k < n) sb.setCharAt(k ++, ' ');
           i = j;
       }
       //If k is preceded by a space, that is, the space after the last word is added, it shall be subtracted by one and deleted together with the following space
       if (sb.charAt(k - 1) == ' ') k --;
       sb.delete(k, n);
       //The second step is to flip the whole string and delete K and the following parts, so the remaining length is k - 1
       reverse(sb, 0, k - 1);
       return sb.toString();
    }
    public void reverse(StringBuffer sb, int l, int r) {
        while (l < r) {
            char c = sb.charAt(l);
            sb.setCharAt(l, sb.charAt(r));
            sb.setCharAt(r, c);
            l ++;
            r --;
        }
    }
}

Method 2:

class Solution {
    public String reverseWords(String s) {
       int n = s.length();
       int left = n - 1, right = n - 1;
       StringBuffer res = new StringBuffer();
       //When the left boundary does not cross the boundary
       while (left >= 0) {
           //Find the first character from back to front, that is, the right boundary of the last word
           while (left >= 0 && s.charAt(left) == ' ') left --;
           //If it has crossed the boundary, it indicates that it does not exist. Retreat directly
           if (left < 0) break;
           right = left;
           //Next, look for the left boundary of the last word and continue to find the first space later
           while (left >= 0 && s.charAt(left) != ' ') left --;
           //Intercept words and put them into the result set [left + 1, right]. Note that substring does not contain the right, so add one
           res.append(new StringBuffer(s.substring(left + 1, right + 1)));
           //Append delimited space
           res.append(' ');
       }
       //Clear the space after the last word
       return res.deleteCharAt(res.length() - 1).toString();
    }
}