剣指offer JZ 52正規表現マッチングPython多解

一.タイトルの説明
'.'を含む関数をマッチングするために実装してください.と'*'の正規表現です.モードの文字'.'任意の文字を表し、'*'はその前の文字が任意の回数(0回を含む)現れることを示します.本題では、マッチングとは、文字列のすべての文字がモード全体に一致することを意味します.例えば、文字列「aaa」は、パターン「a.a」および「ab*ac*a」と一致するが、「aa.a」および「ab*a」と一致しない
二.問題を解く構想.
<1>再帰
まずマッチング可能な集中状況を分析する.
1.sもpatternも空:Trueを返します
2.sは空ではありませんpatternは空です:Falseを返します
3.sは空で、patternは空ではありません:これは一致するかもしれないし、一致しないかもしれません.例えば、「a*b*c*」というpatternは空の文字列に一致することができます(このような気が狂ったテスト例があるかどうか分かりません).この場合はpatternの中に1人おきに*が現れているかどうかを判断すればいいだけです.
特別な状況を議論してから、通常の状況を議論します.
現在一致する位置がs[i]とp[k]であると仮定すると、
sとpatternをpattern[k+1]が「*」である場合と「*」でない場合に分けた.
pattern[k+1]!='*',これは簡単で、s[i]とp[k]が等しいかどうか、あるいはp[k]='.',等しい場合はmatch(s[i+1:end],pattern[k+1:end])を再帰的にマッチングし,
一致しない場合は一致しません.
pattern[k+1]='*'の場合、また3つの状況に細分化されます.
1.s[i]!=p[k],説明'*'ここでの役割のマッチング前の文字数回数は0であり,再帰マッチングmatch(s[i:end],p[k+2:end])
2.s[i]=p[k]の場合、ここで'*'の役割は、前の文字に一致する回数が0であってもよいし、前の文字に一致する数が1であってもよい.
例えば「aa」,「a*aa」のように、この例では「*」がマッチング前の回数が0であり、patternが2ビット後方に移動する.
例えば「aaa','a*aa',この例では'*'がマッチング前回数1として作用し,patternは2ビット後方に移動してもよいし,後方に移動しなくてもよいが,実装ではマッチング回数0と1を結合し,マッチング複数回はn個のマッチング1回に1個のマッチング0回を加えて終了するので,実装ではpatternが後方に移動しなければ再帰的な繰返し回数を減らすことができる.
以上,return match(s[i:end],pattern[k+2:end]or match(s[i+1:end],pattern[k:end]を再帰する必要がある.
<2>動的計画
再帰の考え方と同様に,再帰は上から下への処理方式であり,動的計画は下から上への処理方式である.
動的計画では,正序,すなわち0〜nのものもあれば,n~0逆序のものもある.再帰的な処理を観察するには,いずれも後のいくつかの状況を見なければならないので,この問題は逆順に適している(もちろん順方向でもよい).
解析からも,後から処理を開始すると,現在の処理sの後iがpatternの後kビットであると仮定すると,sのiの前の文字とpatternのkの前の文字が何であるかにかかわらず,iの後とkの後が一致するかどうかの結果には影響しないことが分かった.
s後i文字とpattern後j文字のマッチングをdp[i][j]で表す.
簡単に言えば,sの最後のビットからsの後iビットがpatternの後kビット(k=0~pattern.length)と一致するか否かを判断し,現在の後i+1ビットについては後iビットの状態に基づいて判断する.
dpのサイズはs.length行、pattern.length列.
参考牛客網:
リンク:https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?f=discussion出典:牛客网*は前の认识があって、私达は动态计画で问题を解くことを考えて、动态计画は正方向と逆方向があって、いったいどのように取りますか?*前の再帰呼び出しを参照:match 1(str,i+1,pattern,j+1)はdp[i][j]=dp[i+1][j+1]*に相当する逆遍歴に適しているため、boolean dp[len 1+1][len 2+1]のlen 1=str.length,len 2=patternを初期化することができる.length*はdp[len 1][len 2]=trueを初期化する、str=aaaとpattern=aa*が末尾から「」と「」が必ずtrue*であることを意味する*1を循環する.外部サイクル:aaa*でaaaをマッチングするため、aaaを外部サイクルとし、「」から次のa,aaa,aaa*for(int i=len 1;i>=0;i-)*2をマッチングすることに注意する.内部ループ:aa*を照合する:照合順序"*""a*""aa*"、そこで*for(int j=len 2-1;j>=0;j--)*ループ内部ロジック、参照再帰コール:*=========================================================次が「*」である場合、現在等しいと現在等しくない*1.1に分けられる:現在等しいdp[i][j]=dp[i][j+2]‖dp[i+1][j]*1.2:現在等しくないdp[i][j]=dp[i][j+2]*2.「*」でなければ、現在等しいd[i][j]=dp[i+1][j+1];
主に私たちの外循環はi=s.lengthから始まり、空の文字列からマッチングすることに相当する.空の文字列でも「a*」のようなpatternはマッチングできるので、このような状況を考慮しなければならない.
動的計画の時間複雑度はO(MN)である.
再帰時間の複雑さは指数レベルであり、もちろん最適化できますが、動的計画に似ています.
<3>有限/無限ステータスマシン
巨男のやり方.自分で関連資料を探してください
三.ソースコード

#   
class Solution:
    # s, pattern     
    def match(self, s, pattern):
        # write code here
        if not s and not pattern:return True
        if s and not pattern:return False
        if not s and pattern:
            if len(pattern)>1 and pattern[1]=='*':
                return self.match(s, pattern[2:])
            else:return False
        if len(pattern)>1 and pattern[1]=='*':
            if pattern[0]==s[0] or pattern[0]=='.':
                return self.match(s,pattern[2:]) or self.match(s[1:],pattern)
            else:
                return self.match(s,pattern[2:])
        else:
            if pattern[0]==s[0] or pattern[0]=='.':
                return self.match(s[1:],pattern[1:])
            else:return False

#     
class Solution:
    # s, pattern     
    def match(self, s, pattern):
        # write code here
        if not s and not pattern:return True
        if s and not pattern:return False
        n,m=len(s),len(pattern)
        dp=[[0]*(m+1) for i in range(n+1)]
        dp[n][m]=1
        for i in range(len(s),-1,-1):
            for j in range(len(pattern)-1,-1,-1):
                if j+1