[LeetCode] 151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example 1:
Input: “the sky is blue”
Output: “blue is sky the”

Example 2:
Input: “ hello world! “
Output: “world! hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:
Input: “a good example”
Output: “example good a”
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:
A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

翻转字符串中的单词。

给你一个字符串 s ，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-words-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 正则表达

题意不难理解，我感觉这道题就是要考察代码熟练程度的。

我们要对 input 做预处理，一种情况是去掉 input 前后多余的空格，还有就是单词之间的多余空格也要去掉，每两个单词之间只留一个空格即可。思路是先把 input 字符串分开成数组，再将数组 reverse，最后将数组的每个元素拼接成字符串。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String reverseWords(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return s;
        }

        // normal case
        StringBuilder sb = new StringBuilder();
        // trim 前后 skip 中间的回车 空格之类的东西
        String[] words = s.trim().split("\\s+");
        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i] + " ");
        }
        return sb.toString().trim();
    }
}

思路二 - 双指针

这种思路是 trim 完 input 之后，从后往前开始遍历 input，用双指针卡住单词。先移动其中一个指针，当遇到空格的时候就需要截取单词了；将单词加入结果集之后记得要跳过单词之间的空格。具体参见代码注释。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String reverseWords(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return s;
        }

        // normal case
        // 去掉input边缘无效的空格
        // " test   "
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        // 卡住每个单词的左右指针
        int start = s.length() - 1;
        int end = start;
        while (start >= 0) {
            // 未遇到空格之前，左指针一直往左走
            while (start >= 0 && s.charAt(start) != ' ') {
                start--;
            }
            // 卡住单词，注意subtring是左闭右开的
            String word = s.substring(start + 1, end + 1);
            sb.append(word);
            sb.append(' ');
            // 把左右指针移动到下一个不是空格的位置上接着找下一个单词
            while (start >= 0 && s.charAt(start) == ' ') {
                start--;
            }
            end = start;
        }
        return sb.toString().trim();
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
    return s
        .split(' ')               //create an array of words separated based by spaces
        .filter(string => string) //remove empty strings to take care of extra whitespace
        .reverse()                //reverse the array of words
        .join(' ');               //join the words back together with spaces inbetween
};

[LeetCode] 151. Reverse Words in a String

思路一 - 正则表达

复杂度

代码

思路二 - 双指针

复杂度

代码

相关题目