ぴょこりんブログ

裏垢です。

再帰関数書きたい!!!(発作)

はじめに

再帰関数書きたい!!再帰関数書きたくない?書きたいよね!

パワポを直しても直してもえらいひとからOKが出ないとき、「あぁきれいに記述された再帰関数のように明確なベースケース(終了条件)があれば・・・」とか思っちゃいますよね(???)。

残念ながらお仕事で再帰関数を書く機会など滅多にありません。っていうかそもそもコード書く機会がありませんでしたね(???)。というわけでそんな再帰関数欲求をLeetCodeで解消しましょう!

本日取り扱う問題

10. Regular Expression Matching

こいつを題材に再帰関数欲を満たしていきましょう。正規表現の問題ですね。文字列sと、パターンpを入力として、文字列sがパターンpに合致するか判別する、という問題です。

あ、python3で書きます。

ざっくりした説明

文字列は小文字のアルファベットで構成され、パターンは小文字のアルファベットに加え、"."と"*"という記号が使えます。小文字のアルファベットは文字列とパターンで完全に一致しなければならず、加えて記号に関しては以下ルールが適用されます。

  • ".": あらゆる1文字の代替とできる
  • "*": 直前の文字を任意の回数繰り返せる (0回でもOK)

具体的な入力の例

ざっくり例を挙げていくと以下はOK。

s="aa"
p="aa"

これはダメ(aが1個余る)。

s="aa"
p="aaa"

記号も活用していきましょう。

s="aaaaaa"
p="a*"

a*はaを何度でも繰り替えすことができます。

さぁこれは?

s="b"
p="a*."

これはOK。a*でaを0回繰り返した後、'.'でbを表現と解釈。

最後にこれ。

s="ababvafjldkgdjaf"
p=".*"

これもOK。".*"は"."を繰り返すということで「なんでもいいけど同じやつを繰り返さなきゃいけないのかな?(例えばaaaaやbbbはOKだけど、akafgjsはダメ、みたいな)」と思ったのですが、そんなことはないようです。".*"であらゆる文字列が表現可能というわけですね。

実装

再帰関数と相性のよさそうな問題ですね、なんたって再起関数が書きたいんですから! 今回の主題は「再帰関数書きたい」なので、再帰関数を書いていきましょう。

実装の方針

前から順番にマッチングしていきます。再帰関数で書こうとしたら、前から順にpの文字とsの文字が対応したら、対応した使用済みの部分を取り除いた部分列でマッチングをするといった書き方になるかと。

簡単な例を挙げると、abc, abcを入力として、

match('abc','abc') => match('bc','bc') => match('c','c')=>match('','')

みたいな感じで呼び出していくイメージでしょうか。そんな感じで書いていきましょう。

大雑把に、

  • 文字列かパターンが端っこまで行ったときの処理
  • 文字列とパターンの先頭がマッチしたときの処理
  • 文字列とパターンの先頭がマッチしなかったときの処理

位の場合分けをして書いていきましょう。この場合分けをした意図は、ナイーブに1つ目、3つ目がそれぞれTrueとFalseを返すベースケース、2つ目が再帰的手続きを行うケースと思っていたのですが、例外処理等書いてたらそこまできれいに別れませんでした。たぶんもうちょいきれいな分け方もできると思うのですが、めんどくさいのでこのままいきます。以降、一つずつ説明していきます。

端っこまで行ったときの処理

前述の例からして、最後までうまくマッチできた場合、最終的には空の文字列同士のマッチングを呼び出すことになりそうです。そもそも空の文字列同士でマッチングしたら真を返すのは自然な気がするので、これは良い性質な気もします。

では片方が空でもう片方が空でなかったら偽でしょうか?1ケースだけ例外があります。パターンが空でなく、"*"が使われているケースです。

前述のとおり、"*"は直前の文字の繰り返しを認め、繰り返し回数は0でもOK、すなわちs="", p="*a"などはマッチします。なので、sが空の場合は、もし、pの先頭の文字に"*"がついてたらそれを飛ばしてマッチング、としてあげるとよさそうですね。

先ほどと同じ記法をすると、こんな挙動を期待します。

match('','a*b*c*') => match('','b*c*') => match('','c*')=>match('','')

以上をまとめると、文字列とパターンが端っこに到達したときの処理は以下のようになります。

def match(s,p):
    # 文字列もパターンも空のケース
    if len(s)==0 and len(p)==0:
        return True

    # 文字列のみ空のケース
    elif len(s)==0:
        # "*"なら飛ばす
        if len(p)>1 and p[1]=='*':
            return match(s,p[2:])
        # "*"でなければマッチしない。
        else:
            return False
 # パターンのみ空ならマッチしない
    elif len(p)==0:
        return False

文字列が端っこまで到達したら終わり、がベースケースになるかと思いましたが、パターンが空にならないとダメですね。

先頭がマッチしたときの処理

メジャーな再帰呼び出しのケースかと思います。先頭が一致、またはパターンが"."だったときの対応です。

パターン側の先頭に"*"がついている場合、

  • ①次も同一パターンを使うケース
  • ②次に同一パターンを使わないケース
  • ③そもそもここでこのパターンを使わないケース

があり得ます。3つ目が見落としがちなパターンで、例えば以下のようなケースで使います。

match('ab','a*ab') => match('ab','ab') => match('b','b')=>match('','')

上の例では、"a"と"a*"はマッチしますが、全体での整合性のため、"a*"を使わないマッチングをすることになります。

この3通りを試して、どれかからTrueが返ってこればよいので、

return True in [match(s[1:],p[2:]),match(s[1:],p),match(s,p[2:])]
# 「①のケース、②のケース、③のケースのどれかがTrueかどうか」を返す

なんて書き方をすれば良いでしょう。

パターン先頭に"*"がついていなければ、双方の先頭を除いた部分列を次に投げてあげればよいでしょう。

以上、まとめると、前述のコードに次の手続を付け足すことになります。

    elif s[0]==p[0] or p[0]=='.':
        if len(p)>1 and p[1]=='*':
            return True in [match(s[1:],p[2:]),match(s[1:],p),match(s,p[2:])]
        else:
            return match(s[1:],p[1:])

先頭がマッチしなかったときの処理

基本的には端っこまでいかずに終了してしまうというベースケースです。例外は前述③のような、先頭の文字に"/*"がついていれば、パターン側の先頭がスキップできるので、まだパスをつなげる余地があります。

先頭に'/*'がついていればそれをスキップ、ついていなければ残念ながらFalseといったところですね。前述のコードにさらに以下を付け足します。

        else:
            if len(p)>1 and p[1]=='*':
                return match(s,p[2:])
            else:
                return False

蛇足ですが、前節と似たような手続きが入っているので、「もう少しきれいな場合分けをすればこういう冗長な表現減るかも」とも思うのですが、「働いてない頭でもわかる」という観点では多少冗長でも良いかな、という気もしています。

さて完成・・・あれ?

再帰関数を書くのを楽しんだので、あとはそれをサクッとやってやるのみです。関数を定義したあとは実行するのはこれだけ。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        return match(s,p)

結果は・・・?

f:id:cappsLk:20201102120055p:plain

時間がかかりすぎてるとのことです。コードは冗長な気もしますが、処理自体はさほど冗長なことしてないつもりです。一体何が・・・と思いそうにもなりますが、表示されてるテストケースを見た瞬間、思わずニッコリしてしまいますよね。

"a*"は"a"を何度でも繰り返せるわけです。

"a*a*a*a*a*a*a*a*a*a*a*a*b"

文字列には13個のaが連なっています。たくさんある"a*"に対して、総和が13であれば、それぞれの"a*"にいくつのaを割り当てても良い状況になっています。ちょっとした組み合わせ爆発が起きているわけですね。

そもそも"a*"が連続しているというのが冗長な表現で、連続していくつ"a*"が並んでも、"a*"が一つあるのと表現力は変わらないんですよね。なので、連続して「同じ文字+"*"」が出現したら一つ先にスキップする、という表現を付け加えましょう。

            if p[:2]==p[2:4]: # 次の文字も同一で"*"がついてる場合
                return match(s,p[2:]) #前方を飛ばす

この2行を

if len(p)>1 and p[1]=='*':

なところ、つまりパターン先頭の文字または記号に*がついてるケース追加するだけで膨大なパターンが勝手に縮退してくれます。

match('aaab','a*a*a*b') =>match('aaab','a*a*b') =>match('aaab','a*b')

連続する最後の"a*"のみが残るまで勝手に縮退してくれた後、

match('aaab','a*b') =>match('aab','a*b') =>match('ab','a*b') =>match('b','b')

となるので、先ほどの組み合わせ爆発が回避できると。

パターン先頭の文字または記号に*がついてるケース、3回登場してるので、丁寧に場合分けすれば1か所の修正で済んだと思うと、やっぱ考え抜かれた場合分けは保守性を上げますね(掌返し)。

と言いつつ、

  • 文字列が空でパターンだけ残ってるケース
  • 普通に文字列とパターンの先頭がマッチしてるケース
  • 普通に文字列とパターンの先頭がマッチしてないケース

の3か所で上述のif文は出てきており、真ん中以外はいずれにしてもスキップするだけなので、この修正は真ん中だけやれば早くなります。 f:id:cappsLk:20201102122834p:plain

やったね!

def match(s,p):
    # 文字列もパターンも空のケース
    if len(s)==0 and len(p)==0:
        return True

    # 文字列のみ空のケース
    elif len(s)==0:
        # "*"なら飛ばす
        if len(p)>1 and p[1]=='*':
            return match(s,p[2:])
        # "*"でなければマッチしない。
        else:
            return False
    
    #パターンのみ空ならマッチしない
    elif len(p)==0:
        return False
    
    # 先頭が一致(またはワイルドカード"."のケース)
    elif s[0]==p[0] or p[0]=='.':
        if p[:2]==p[2:4]: # 次の文字も同一で"*"がついてる場合
            return match(s,p[2:]) #前方を飛ばす

        if len(p)>1 and p[1]=='*':
            return True in [match(s[1:],p[2:]),match(s[1:],p),match(s,p[2:])]
        else:
            return match(s[1:],p[1:])

    # それ以外、つまり先頭がマッチしないケース
    else:
        if len(p)>1 and p[1]=='*':
            return match(s,p[2:])
        else:
            return False

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        return match(s,p)

時間があったらもうちょい整理できないか考えたかったんだけど時間が無かったのでここまで。

まとめ

LeetCodeを始めた初日にこの問題にあたったんですが、「テストで意地悪なケースに引っ掛かり」「その対応策として簡単に実装できる方法を思いついた」、すなわち楽しく解けた印象的な問題だったので、何となく記事にしてみました。みんなもLeetCodeをやって転職しましょう(?????)。