151. Reverse Words in a String

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

Question

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.

初想法

第一思路是用正则去做，匹配出非空的字符串，然后reverse一下：

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
    const groups = Array.from(s.match(/\S+/g));
    return groups.reverse().join(' ');
};

双指针

这道题也可以用双指针来做:

• 一个指针指向当前有效的字符串，一个指针往前走
• 当字符串有效值，同步两个指针
• 当字符串无效时，如果指针相同，说明是一个有效的词，推入结果数组

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let ret = '';
    let p1 = s.length - 1;
    let p2 = s.length - 1;
    while (true) {
        if (s[p1] === ' ') {
            for (let i = p1 + 1; i <= p2; i++) ret += s[i];
            if (ret[ret.length - 1] !== ' ') ret += ' ';
            p1 -= 1;
            p2 = p1;
        } else if (s[p1] === undefined) {
            for (let i = p1 + 1; i <= p2; i++) ret += s[i];
            return ret.trim();
        } else {
            p1 -= 1;
        }
    }
};

总结

正则中一些常见的替代字符要熟悉，非常有用。

这道题的双指针比较简单和典型，要熟悉基础题型。