给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格

 

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb=removeSpace(s);

        reverseString(sb,0,sb.length()-1);
        reverseEachWord(sb);

        return sb.toString();
        
        
    }
    private StringBuilder removeSpace(String s){

        
        int start=0;
        int end=s.length()-1;
        while(s.charAt(start)==' ')start++;
        while(s.charAt(end)==' ') end--;
        StringBuilder sb=new StringBuilder();

        while(start<=end){
            char c=s.charAt(start);
            if(c!=' '||sb.charAt(sb.length()-1)!=' '){
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    public void reverseString(StringBuilder sb,int start,int end){
        while(start<end){
            char temp=sb.charAt(start);
            sb.setCharAt(start,sb.charAt(end));
            sb.setCharAt(end,temp);
            start++;
            end--;
        }
    }
    private void reverseEachWord(StringBuilder sb){
        int start=0;
        int end=1;
        int n=sb.length();
        while(start<n){
            while(end<n&&sb.charAt(end)!=' '){
                end++;
            }
            reverseString(sb,start,end-1);
            start=end+1;
            end=start+1;
        }
    }
}