タイトルの通り、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
考え方としては、再帰の解き方と似ていますが、実は違いますね。
参考