LeetCode刷题【151】翻转字符串里的单词

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

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

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

说明：

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

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 4：

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：

• 请尝试使用 O(1) 额外空间复杂度的原地解法。

public String reverseWords2(String s) {
        String[] arr = s.split(" ");
        if (arr.length == 1){
            return arr[0];
        }
        StringBuilder sb = new StringBuilder();
        sb.append(arr[arr.length-1]);
        int i = arr.length-2;
        while (i >= 0) {
            if (arr[i].length()>0){//判空很重要
                sb.append(" ").append(arr[i]);
            }
            i--;
        }
        return sb.toString();
    }

O（1）空间的java里面应该是实现不了，如果哪位大神有啥思路的可以提供下，我就整出来个char[]上原地翻转实现的，而且最后还是的new String ,再trim()实现

思路是这样的，先把String型的字符转成char[]，在这过程中需要把中间重复的空格去掉，或者说是挪到char[]的结尾部分。写了一个moveRedundantSpace方法，把中间多余的空格去除掉，或者说挪到数组结尾。

然后对char[]数组从头到整体翻转，然后再次遍历，根据空格判断单词分割，分别对每个单词重新翻转，这样单个单词的字符顺序就翻转回来了。代码里面这边的单词翻转部分是在写去除重复空格之前写的，所以还保留了之前有重复空格时候的do/while判断。

  class Solution {
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        moveRedundantSpace(arr);
        int left = 0;
        int right = arr.length-1;
        reverse(arr,left,right);

        //挨个单词翻转
        int index1;
        int index2;
        int i = 0;
        while (i <= arr.length-1){
            if (arr[i] != ' ') {
                index1 = i;
                do {
                    i++;
                } while (i <= arr.length - 1 && arr[i] != ' ');
                index2 = i-1;
                reverse(arr,index1,index2);
            }
            i++;
        }
        return (new String(arr)).trim();
    }

    public void reverse(char[] arr, int left ,int right){
        while (left < right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }

    public void moveRedundantSpace(char[] arr){
        int cur = 1;
        for (int index = 1;index < arr.length; index++){
            while (cur < arr.length && arr[cur] == ' ' && arr[cur-1] == ' '){
                cur++;
            }
            if (cur < arr.length){
                arr[index] = arr[cur];
            }else{
                arr[index] = ' ';
            }
            cur++;
        }
    }
}