# LeetCode Easy 344. Reverse String

tags: leetcode

ということで今回からはRecursion Iの問題を扱おうと思います

再帰関数

再帰関数に関係する問題を解くので前回の再帰関数に関して扱った記事を読んでくれると再帰関数について苦手意識がなくなっていいかもしれません

propyon.hateblo.jp

再帰関数を使うケースでは2つの点考えれば良いです

• 再帰的に定義できるか
• 再帰関数を通るたびに問題が簡単になっているか

以上です

問題

ExploreからのURLだとこちら

普通のURLだとこちら

文字列を反転させる関数を書け.入力の文字列はchar[]型である

入力以外のデータ構造を使わずに空間計算量が$O(1)$になるようにして入力文字列を変換する関数に設計せよ

解法

これは再帰関数を使った問題として考えるまずは何が解決された状態かを考えます

• reverseされた文字列

これがゴールです.そして次にどのようにして再帰的に表現するかを考えます

これはreverseされた文字列をどう考えるかと同じです

ということで詳しい解法は以下の通り

• 文字列を反転する際,文字列の先頭と末尾を交換すれば良いです
• 反転していない文字列と反転した文字列の境界線の添字を使えばreverseされた文字列になっているかどうかが使えます
  • まだ反転していない文字列の左端をleft
  • まだ反転していない文字列の右端をright
  • とします
• そしてleftとrightを交換します
  • つまりleftとrightまでは文字列が反転したことになります
• 再帰的にleftをincrement, rightをdecrementします
  • left < rightまで実行すれば良いです
• 入力文字列の長さを$n$とします
  • 空間計算量は再帰関数でStackを使うので$O(n)$
  • 時間計算量は文字列の交換を最大$n/2$回行うので$O(n)$

Python

Pythonではinner functionを使います

helperと命名されることが多いので慣習に倣います

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def helper(s, left, right):
            if (left < right):
                s[left], s[right] = s[right], s[left]
                helper(s, left+1, right-1)
                
        helper(s, 0, len(s)-1)

C++

privateを使います

class Solution {
public:
    void reverseString(vector<char>& s) {
        int last = s.size() - 1;
        helper(s, 0, last);
    }
private:
    void helper(vector<char>& s, int left, int right) {
        if (left < right) {
            swap(s[left], s[right]);
            helper(s, left+1, right-1);
        }        
    }
};

解法2(not 再帰)

再帰を使わないで同じことを書けます

その方が短いですし,この問題はそもそも再帰を使わない方が良いと思います

• 入力文字列の長さを$n$とします
  • 空間計算量は再帰関数でStack領域を使わないので$O(1)$
  • 時間計算量は変わらず$O(n)$

Python

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

C++

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0; i < s.size()/2; i++) {
            swap(s[i], s[s.size()-i-1]);
        }
    }
};

解法3(意味なし)

メソッドや組み込み関数を使う

Python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

C++

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

ちなみに

全く同じ問題がK&Rにあります

https://github.com/diohabara/ansi_c/blob/master/chap4/ex4-13.c