LeetCode.151.Reverse Words in a String 翻转字符串里的单词

题目描述

151 Reverse Words in a String
https://leetcode-cn.com/problems/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.

Follow up:
For C programmers, try to solve it in-place in O(1) extra space.

---

解题过程

使用编程语言的库函数

直接用 Java 集合类来实现。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    public String reverseWords(String s) {
        if (null == s) {
            return null;
        }
        List<String> wordsList = Arrays.asList(s.trim().split(" "));
        Collections.reverse(wordsList);
        return wordsList.stream().filter(word -> !word.isEmpty()).collect(Collectors.joining(" "));
    }
}

官方题解代码如下：

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

看了官方题解后，发现自己的代码还是不够精简，有好多可以改进的地方：

1、我的 split() 使用的是固定的一个空格，有可能分隔出空字符串，之后还需要过滤一下，其实可以用一个正则表达式 "\\s+" 或 + 直接匹配1个或多个空白字符

2、我最后为了用空格把反转后的字符串列表串接起来，用了 Stream ，其实根本不需要，Java 8 开始 String 类直接提供了一个 join(" ", List) 方法，直接就可以串接。

两次反转(单词反转+整体反转)

栈

---

GitHub代码

algorithms/leetcode/leetcode/_151_ReverseWordsInString.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_151_ReverseWordsInString.java

---