# 151. Reverse Words in a String

### Leetcode

<https://leetcode.com/problems/reverse-words-in-a-string/>

### 題目

Given an input string `s`, reverse the order of the **words**.

A **word** is defined as a sequence of non-space characters. The **words** in `s` will be separated by at least one space.

Return *a string of the words in reverse order concatenated by a single space.*

**Note** that `s` may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

**Follow-up:** If the string data type is mutable in your language, can you solve it **in-place** with `O(1)` extra space?

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

套用內建方法

```
var reverseWords = function(s) {
    return s.split(" ").reverse().filter(w => w !== "").join(" ");
};
```

Runtime: 167 ms, faster than 5.14% of JavaScript online submissions for Reverse Words in a String.

Memory Usage: 39.4 MB, less than 99.93% of JavaScript online submissions for Reverse Words in a String.

* **方法二**

將字串轉換為矩陣，再把矩陣反轉過來後變回字串

```
var reverseWords = function(s) {
    s = s.trim();
    const arr = [];
    let temp = '';
    for(let i=0; i<s.length; i++) {
      if (i===0) {
        temp = s[i];
        continue;
      }

      if(s[i-1] !== ' ' && s[i] === ' ') {
        arr.push(temp);
        temp = '';
      } else if (s[i] !== ' ') {
        temp += s[i];
      }
    }
    arr.push(temp);
    
    for(let i=0; i<arr.length/2; i++) {
        const j = arr.length-i-1;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    return arr.join(' ');
};
```

Runtime: 123 ms, faster than 15.97% of JavaScript online submissions for Reverse Words in a String.

Memory Usage: 40.9 MB, less than 25.10% of JavaScript online submissions for Reverse Words in a String.

* **方法三**

從右邊開始遍歷產出由右而左的字串

```
var reverseWords = function(s) {
    s = s.trim();

    let word = '';
    let left = right = s.length;
    while(right > 0) {
      while(s[left] !== ' ' && left >= 0) left--;
      word += s.substring(left+1, right); 
      while(s[left] === ' ') left--;
      right = left+1;
      word += ' ';
    }

    return word.trim();
};
```

Runtime: 92 ms, faster than 48.33% of JavaScript online submissions for Reverse Words in a String.

Memory Usage: 40.3 MB, less than 62.90% of JavaScript online submissions for Reverse Words in a String.

### 測資

```
let s = "a good   example";
s = "a b c   example";
s = "  Bob    Loves  Alice   ";
s = "Alice does not even like bob";

console.log(reverseWords(s))
```
