タイトルの通り、LeetCode 344の解き方についてシェアしてきます。

問題文はそのままコピーします、

Write a function that reverses a string. The input string is given as an array of characters s.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
 

Constraints:

1 <= s.length <= 105
s[i] is a printable ascii character.

ま、簡単に言うと、string型の'hello'を'olleh'で変換することです。

各言語内の関数やモジュールを使えばええじゃんと思うかもしれないが、実はこれを実現するためにはいろいろな方法があります。

今回は2つの方法を紹介します、一つはタイトルの通り再帰で実現します。もう一つはTwo pointersで実現します。

Recursion solution

Recursionの概念はわかると思いますが、ざっくりで言うと、

関数内部にもう一度今所属している関数を呼び出す。
2．永遠に呼び出されたらキリがないので、必ずなにか終わりの条件を追加する。

実はこの問題に関して、Two pointersのやり方は多分理解しやすいが、Recursionで実現するのも面白いです。

では、大体のイメージ図からどのように再帰で実現したかをみてみましょう！

解説：

まず、1回目の再帰はhとoを同時に再帰します(多分理解にくいが、コード見ればわかると思います)。

2回目に入って、また再帰し、lのところで再帰が止まります。

止まったら、今回は元に戻します。

ここで、2回目の再帰の部分はeとlを交換し、1回目はhとoを交換します。

それで終了となります。

コード：

def recursion(s, left, right):
        if left >= right:
            return
        recursion(s, left+1, right-1)
        s[left], s[right] = s[right], s[left]

left >= rightが再帰の終了条件。
4行目の部分は再帰の部分で、毎回の再帰は左側を右に1 step,　右側は左に1 stepの形ですすみます。
再帰が終了した後(left < rightの時)、各文字を交換します。

Two pointers

def recursion(s, left, right):
    while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

    return s

考え方としては、再帰の解き方と似ていますが、実は違いますね。

参考