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?

解答

• 方法一

套用內建方法

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))