剣指Offer 19.正規表現マッチング(Python)

タイトル紹介
含む関数をマッチングするための関数を実装してください.と*の正規表現です.モードの文字任意の文字を表し、*はその前の文字が任意の回数(0回を含む)現れることを示します.本題では、マッチングとは、文字列のすべての文字がモード全体に一致することを意味します.

   "aaa"   "a.a" "ab*ac*a"  ；
   "aaa" "aa.a" "ab*a"    。

タイトル解読
私たちはまず*文字から始めることができます.*文字は対するからです.文字は複雑で、状況も多い.まず、最初の文字の後に*文字であるかどうかで、2つの状況に分けて、この2つの状況について議論します.
1.先頭文字の後(つまり2文字目)が*文字の場合、文字列とpatternの先頭文字が等しいかどうかを判断し、等しくなければ、patternを2文字後ろに移動してこそ、マッチングに成功する可能性がある.最初の文字が等しい場合(.等しいと見なすこともできます)、次の3つのマッチングモードがあります.

patternの最初の2文字、すなわち*の前の文字を直接スキップして0回と見なす.

文字列は1文字後ろに移動し、patternは2文字後ろに移動し、*の前に現れる文字を1回と見なす.

文字列が1文字後ろに移動し、patternは動かず、*前の文字が複数回現れると見なされます.

次の4つの例を組み合わせると、よりはっきり見えます.

    “aabb”
pattern1: c*aabb 	      ，   pattern      ；
pattern2: a*aabb 	         ，      *          0 ，      ；
pattern3: a*abb		     ，  *          1 ，      ；
pattern4: a*bb		     ，       *            （2    ），      。

以上の4つの場合,最後のいずれかのマッチングに成功するとTrueを返す.
2.先頭文字(つまり2番目の文字)が*文字でない場合、文字列とpatternの2つの先頭文字を直接比較できます.

が等しい場合、両者はいずれも1文字後ろに移動し、次の比較を行う.

等しくなければ、Falseに直接戻ることができます.

    “abcd”
pattern1: abcd		     a，       ；
pattern2: bbcd		      ，    False。

コード解析

    def match(self, s, pattern):
    	#       
        if s == pattern: return True
        if not pattern: return False
        #            *
        if len(pattern)>1 and pattern[1] == '*':
        	#          ，     .    
            if s and (pattern[0] == s[0] or pattern[0] == '.'):
            	#       ，      
                return self.match(s[1:],pattern[2:]) \
                        or self.match(s,pattern[2:]) \
                        or self.match(s[1:], pattern)
            else:
            	#    ，   pattern  ，    
                return self.match(s, pattern[2:])
        #         *，              
        elif s and (s[0] == pattern[0] or pattern[0] == '.'):
            return self.match(s[1:], pattern[1:])
    
        return False