# 0151. Reverse Words in a String
###### tags: `Leetcode` `Microsoft` `Medium`
Link: https://leetcode.com/problems/reverse-words-in-a-string/
## 思路
只要按照题目要求来就可以做出来
### 思路一
用trim，split和reverse
**有非常多新奇的语法 体现了java的酷炫**
### 思路二
手动自己写函数
### 思路三 双端队列
**注意语法**
## Code
### 思路一

class Solution {
    public String reverseWords(String s) {
        //去除前后空白
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        //list 将需要转化的数组作为参数
        //split() 方法用于把一个字符串分割成字符串数组
        // \\s代表空格，+号代表一个或者多个
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ",wordList);
    }
}

### 思路二

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

        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);

        // 翻转每个单词
        reverseEachWord(sb);

        return sb.toString();
    }

    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 将字符串间多余的空白字符去除
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }

    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        while (start < n) {
            // 循环至单词的末尾
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 翻转单词
            reverse(sb, start, end - 1);
            // 更新start，去找下一个单词
            start = end + 1;
            ++end;
        }
    }
}

### 思路二
定义[left,right]为需要读取单词的区间
指针left、right定义为在去掉字符串首尾空格后字符串的首尾位置
1.去掉字符串首尾左右空格，移动left、right指针指向去掉空格后的首尾位置。
while（left<=right）{
2.从后往前一个个遍历单词，设置index指针，指向right位置，index从后往前遍历，直到遇到空格或者末尾
说明此时已经将其中一个单词遍历完。
3.此时index+1为该单词的首位，遍历字符串[index+1,right]区间，加入到StringBuffer中
4.判断index位置，加入空格：若index位置已经到达头位置了，说明不需要添加空格，否则都需要添加空格隔开单词
5.index继续从后往前遍历，跳过空格直到遇到非空字符，将right指向index的位置执行下一次循环
}
6.返回StringBuilder.toString();

class Solution {
    public String reverseWords(String s) {
        StringBuffer sb = new StringBuffer();
        int start = 0, end = s.length()-1;
        while(s.charAt(start)==' ')start++;
        while(s.charAt(end)==' ')end--;
        int idx = end;
        while(start<=end){
            while(idx>=start && s.charAt(idx)!=' '){
                idx--;
            }
            for(int i = idx+1;i <= end;i++){
                sb.append(s.charAt(i));
            }
            if (idx+1 != start) {
                sb.append(' ');
            }
            while(idx>=start && s.charAt(idx)==' ')idx--;
            end = idx;
        }
        return sb.toString();
    }
}

### 思路三

class Solution {
    public String reverseWords(String s) {
        int left = 0, right = s.length()-1;
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }
        Deque<String> d = new ArrayDeque<>();
        StringBuffer sb = new StringBuffer();
        while(left<=right){
            char c = s.charAt(left);
            if(sb.length()!=0 && c==' '){
                d.offerFirst(sb.toString());
                sb.setLength(0);
            }
            else if(c != ' '){
                sb.append(c);
            }
            ++left;
        }
        d.offerFirst(sb.toString());
        return String.join(" ",d);
    }
}