Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 151. Reverse Words in a String

tags: leetcode

問題

イデア

「文字列が与えられるので,空白で区切られた単語を反転させて返せ」という問題です.

最初は完全に問題を勘違いして

" ".join([word[::-1] for word in s.split()])

と書いていました…単語の順番を反転させます.

解法

  • 文字列を空白区切りで分けます.
  • その文字列を配列にして,配列の要素の順番を反転させます.
  • そして,先頭の文字列から空白区切りで連結させます.

計算量

文字列の数を$N$,文字列の最大長を$S$とします.

  • 時間計算量
    • 分割に$O(N)$
    • 順番を反転に$O(N)$
    • 連結に$O(N)$
    • 全て合わせて$O(N)$です.
  • 空間計算量
    • 新しく配列を作るので$O(NS)$です.

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([word for word in s.split()][::-1])