劍指 Offer 19. 正則表達(dá)式匹配

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包含'. '和'*'的正則表達(dá)式。模式中的字符'.'表示任意一個(gè)字符，而'*'表示它前面的字符可以出現(xiàn)任意次（含0次）。在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但與"aa.a"和"ab*a"均不匹配。

感覺(jué)題意其實(shí)蠻難理解的。截個(gè)圖：

是比較復(fù)雜的動(dòng)態(tài)規(guī)劃，做了下筆記和注釋。

class?Solution:

????def?isMatch(self,?s:?str,?p:?str)?->?bool:

????????#?要判斷字符串是否匹配，可以用動(dòng)態(tài)規(guī)劃進(jìn)行判斷

????????#?dp[i][j]對(duì)應(yīng)s[i-1]和p[j-1]對(duì)應(yīng)的字符串是否匹配。

????????#?①p[j-1]=='*'

????????#?1.視作p字符串倒數(shù)第二個(gè)字符出現(xiàn)了零次，則不需要判斷是否相等了。

????????#?eg:s[]=abcde

????????#?p[]=abcdf*e?此時(shí)f*視作f出現(xiàn)零次

????????#?這個(gè)情況下：dq[i][j]=dp[i][j-2]

????????#?2.視作p字符串倒數(shù)第二個(gè)數(shù)出現(xiàn)了兩次

????????#?eg:s[]=abcdd

????????#?p[]=abcd*?此時(shí)d*視作d出現(xiàn)了兩次

????????#?3..代表任意字符，并出現(xiàn)了兩次

????????#?eg:s[]=abc

????????#?p[]=abc.*?此時(shí).*視作為空

????????#?②p[j-1]!='*'

????????#?1.d[i-1][j-1]并且s[i-1]=p[j-1]

????????#?eg:s[]=abcde

????????#?p[]=abcde

????????#?2.d[i-1][j-1]并且p[j-1]

????????#?eg:s[]=abcde

????????#?p[]=abcd.?此時(shí).視作e，可以匹配

????????#?③初始化的時(shí)候

????????#?dp[0][0]=0

????????#?并且當(dāng)p偶數(shù)位為'*'時(shí)，可以視作出現(xiàn)0次，所以p如果為偶數(shù)位都為*時(shí)，可以匹配空字符串

????????m=len(s)+1

????????n=len(p)+1

????????dp=[[False?for?col?in?range(n)]for?row?in?range(m)]

????????dp[0][0]=True

????????for?j?in?range(2,n,2):

????????????dp[0][j]=dp[0][j-2]?and?p[j-1]=='*'

????????for?i?in?range(1,m):

????????????for?j?in?range(1,n):

????????????????if?p[j-1]=='*':

????????????????????if?dp[i][j-2]:dp[i][j]=True

????????????????????elif?dp[i-1][j]?and?s[i-1]==p[j-2]:dp[i][j]=True

????????????????????elif?dp[i-1][j]?and?p[j-2]=='.':dp[i][j]=True

????????????????else:

????????????????????if?dp[i-1][j-1]?and?s[i-1]==p[j-1]:dp[i][j]=True

????????????????????elif?dp[i-1][j-1]?and?p[j-1]=='.':dp[i][j]=True

????????return?dp[m-1][n-1]