AI毛毛的blog

leetcode打卡-0151翻转字符串里的单词

题目描述

给定一个字符串，逐个翻转字符串中的每个单词。

说明：无空格字符构成一个单词；输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括；如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例：

输入：s = "  Bob    Loves  Alice   "

输出："Alice Loves Bob"

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-words-in-a-string

解题思路

1. 无情的API调用工程师

字符串的分解拼接，大多数高级语言本身或者其标准库内，都有对应的实现，这题可以考虑直接分解字符串s，翻转后再合并成字符串，以Python为例。

1
2
3
class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))

一行搞定，简单明了，Python真是拯救头发的好语言。

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

151_01.png

用Rust也能写，就是复杂一点。

1
2
3
4
5
impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.trim().split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>().into_iter().rev().collect::<Vec<String>>().join(" ")
    }
}

2. 双端队列或者栈

涉及到翻转的问题，可以考虑用栈的前进后出的特性来解决，此题中遍历原字符串，拆分单词，压入栈中，然后弹出组成新字符串即可。

不过Python中的双端队列效率也挺高，按照左端插入的方式，也能得到类似的效果，将单词一个个压入队列头部，最后转成字符串处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def reverseWords(self, s: str) -> str:
        left = 0
        right = len(s) - 1
        # 去掉字符串开头的空白字符
        while left <= right and s[left] == ' ':
            left += 1
        
        # 去掉字符串末尾的空白字符
        while left <= right and s[right] == ' ':
            right -= 1
            
        d = collections.deque()
        word = []

        # 将单词push到队列的头部
        while left <= right:
            if s[left] == ' ' and word:
                d.appendleft(''.join(word))
                word = []
            elif s[left] != ' ':
                word.append(s[left])
            left += 1
        d.appendleft(''.join(word))
        
        return ' '.join(d)
  • 时间复杂度O(n)
  • 空间复杂度O(n)

151_02.png

还没学到Rust该怎么写双端队列，后面学会了再来补充一下。