leetcode

どーも!

たかぽんです!

今回もやっていこうと思います!

344. Reverse String

本日の問題は以下。

やることとしては、単純に配列の要素として文字をもつリストが渡されるので、その値を逆順にしたリストを返せ...といったものです。

いつも通り、例をお借りすると...

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

上記のように、Inputでhelloという文字が要素として保持されていて、それをひっくり返したOutputを出せ。

といった問題ですね。

ただし...

一つだけ大切な条件があります。

Do not allocate extra space for another array, 
you must do this by modifying the input array in-place with O(1) extra memory.

つまり、別の配列を作ってなんかしたりしちゃだめですよ〜!と。

与えられたinputの配列そのものを編集して、Outputの形にする必要があります。

筆者の得意分野が潰されました...w

というわけで、問題はなんとなくわかったかと思います。それでは、アルゴリズムを検討していきましょう。

アルゴリズム

筆者が思いついた方法だと、まず最初に配列の要素数分ループを回すのですが、その際に末尾から順番に値を取得していきます。

そして、順番に取得する値をそれぞれ都度末尾に追加していきます。

そうすることで...

['h', 'e', 'l', 'l', 'o']  // オリジナル
['h', 'e', 'l', 'l', 'o']  // oを取り出して末尾につける
['h', 'e', 'l', 'o', 'l']  // 後ろのlを取り出して末尾につける
['h', 'e', 'o', 'l', 'l']  // 手前のlを取り出して末尾につける
['h', 'o', 'l', 'l', 'e']  // eを取り出して末尾につける
['o', 'l', 'l', 'e', 'h']  // 完成!

のようになるイメージです。

初回に関しては末尾を取得して、末尾に追加するという不毛なことをやってしまっていますが、いったん目を瞑ります...w

手元で取ったメモだとこんな感じです。

都度sのオリジナルのリストを書き換えていくのですが、ちゃんとデクリメントさせることによって、後ろに追加し多分が逆順に整列されているイメージですね。

気をつけないといけないのが、s自体を編集しているため、下手にpopしてしまうと、編集後のpopになります。

そのため、初期のhelloのpop(2)はeですが、例えば上記の4段階目にあるsのappend後"holle"の場合は、sの中身がholle"なので、pop(2)はoになります。

そこに気をつけて処理をかければうまくできるかと思います。

提出したコード

最後に提出したコードを以下に載せておきます。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i, char in enumerate(s):
            popped = s.pop(len(s) -1 - i)
            s.append(popped)
        return s

# 結果
Runtime: 424 ms, faster than 5.16% of Python3 online submissions for Reverse String.
Memory Usage: 18.5 MB, less than 81.19% of Python3 online submissions for Reverse String.

おすすめの記事