Leetcode - 151. 翻转字符串里的单词

class Solution {

    // 主要思路：先对整个字符串进行翻转，然后再对得到的字符串中各个单词进行翻转
    // 原来的字符串："the sky is blue"
    // 翻转该字符串："eulb si yks eht"
    // 翻转各个单词："blue is sky the"
    // 翻转整个字符串时，如果有多余的空格，则可以顺便去除多余空格
    public String reverseWords(String s) {
        char[] arr = new char[s.length()];
        int len = 0;
        char pre = ' ';
        
        // 对字符串s进行反转，同时去除多余空格，将结果存到arr中
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c != ' ' || pre != ' ') {
                arr[len++] = c;
            }
            pre = c;
        }

        // 如果最后添加到arr中的是个空格，则将该空格去掉
        if (pre == ' ') {
            len--;
        }
        
        // 重新遍历arr数组，反转里面的单词
        int begin = 0;
        for (int end = 1; end <= len; end++) {
            if (end == len || arr[end] == ' ') {
                reverse(arr, begin, end - 1);
                begin = end + 1;
            }
        }
        return new String(arr, 0, len);
    }

    private static void reverse(char[] arr, int l, int r) {
        while (l < r) {
            swap(arr, l++, r--);
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }
}