翻转字符串中的单词-蒲公英云

翻转字符串中的单词

题目：给你一个字符串 s ，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

解题思路：拆分

先去除字符串首尾，以及中间多余的空格
翻转整个字符串
翻转字符串中的每个单词

代码：

class Solution {
    public String reverseWords(String s) {
        // 去除首尾及中间多余的空格
        StringBuilder sb = removeSpace(s);
        // 翻转整个字符串
        reverse(sb, 0, sb.length()-1);
        // 翻转每个单词
        reverseEachWord(sb);
        // 返回最终字符串
        return sb.toString();
    }
    // 去除首尾及中间多余的空格
    private StringBuilder removeSpace(String s){
        int start = 0, end = s.length()-1;
        while(s.charAt(start) == ' ') start++; // 去除头部空格
        while(s.charAt(end) == ' ') end--; // 去除尾部空格
        StringBuilder sb = new StringBuilder();
        while(start <= end){
            char ch = s.charAt(start);
            if(ch != ' ' || sb.charAt(sb.length()-1) != ' '){
      // 追加当前不是空格的字符，以及前一个不是空格的空格
                sb.append(ch);
            }
            start++;
        }
        return sb;
    }
    // 翻转字符串的指定子串
    private void reverse(StringBuilder sb, int start, int end){
        while(start < end){
            char ch = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, ch);
            start++;
            end--;
        }
    }
    // 翻转每个单词
    private void reverseEachWord(StringBuilder sb){
        int len = sb.length();
        int start = 0, end = 1;
        while(start < len){
            while(end < len && sb.charAt(end) != ' '){
                end++;
            }
            // 翻转单词
            reverse(sb, start, end-1);
            // 寻找下一个单词
            start = end + 1;
            end = start + 1;
        }
    }    
}