文字列の単語を逆順に並べ替える - LeetCode 151

空白で区切られた単語の順を逆にして、空白 1 つでつなぎ直す。文字列を前から読んで、単語の始まりと終わりを自分で見つける練習です。

海外で定番の問題リスト 4 本のうち 1 本に入っています (LeetCode Top Interview 150)

問題

文字列 s を受け取ります。s は、空白で区切られたいくつかの単語でできています。単語の順を逆にして、単語と単語の間を空白 1 つでつないだ文字列を返す関数を書いてください。

  • 単語は、空白を含まない 1 文字以上のひとまとまりです
  • 先頭と末尾の空白は捨てます。単語の間に空白が 2 つ以上続いていても、返す文字列では 1 つにします
  • 単語が 1 つも無いときは、空の文字列を返します
  • s の長さは 0 以上 10000 以下で、英字、数字、半角の空白だけでできています

入力と出力の例

例 1

入力

s = "cats like warm milk"

出力

"milk warm like cats"

例 2

先頭と末尾の空白は消え、続いた空白は 1 つになります。

入力

s = "  open   the door "

出力

"door the open"

例 3

単語が 1 つだけなら、そのまま返します。

入力

s = "hello"

出力

"hello"

図で見る

例 1 で、解き方がどう動くか。押すと大きく開きます。

面接での聞かれ方

面接では、短い一言で渡されることが多いです。

  • 「文の単語の順番を逆にしてください」
  • 書き終えたあとに「split を使わずに書けますか?」と続けて聞かれます
  • 「空白が続いていたら?」「空の文字列なら?」と、端の場合を聞かれることもあります

単語の中の文字まで逆にするのか、単語の順だけを逆にするのかを、最初に確かめておくと安心です。空白の扱いも、書き始める前に口で決めておきます。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

  1. ヒント 2

  2. ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

main.py
def reverse_words(s: str) -> str:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(reverse_words("cats like warm milk"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します