1 題目描述

2 解題思路

題目中的匹配是一個逐步匹配的過程：我們每次從字符串?p?中取出一個字符或者一個字符 &?星號的組合，并在?s?中進行匹配。

對于?p?中一個字符而言（包括字符.），它只能在?s?中匹配一個字符，匹配的方法具有唯一性。

而對于?p?中字符 &星號的組合而言，它可以在?s?中匹配任意自然數個字符，并不具有唯一性。

因此我們可以考慮使用動態規劃，對匹配的方案進行枚舉。

?

我們用 f[i][j] 表示 s 的前 i個字符與 p 中的前 j個字符是否能夠匹配。

在進行狀態轉移時，我們考慮 p 的第 j 個字符的匹配情況：

1）如果?p?的第?j個字符是一個字母，那么我們必須在?s?中匹配一個相同的字母，即

也就是說，如果 s 的第 i個字符與 p?的第 j 個字符不相同，那么無法進行匹配；否則我們可以匹配兩個字符串的最后一個字符，整體s和整體p匹配與否取決于s和p前面i-1和j-1個字符的匹配與否。

2）如果?p?的第?j?個字符是?*，那么就表示我們可以對?p?的第j?1?個字符匹配任意自然數次。

在匹配?0?次的情況下，我們有：f[i][j]=f[i][j?2]

在匹配?1,2,3??次的情況下，類似地我們有

如果我們通過這種方法進行轉移，那么我們就需要枚舉這個組合到底匹配了 s?中的幾個字符，會增導致時間復雜度增加，并且代碼編寫起來十分麻煩。

我們不妨換個角度考慮這個問題：字母 &星號的組合在匹配的過程中，本質上只會有兩種情況：

• 匹配?s?末尾的一個字符，將該字符扔掉，而該字母 &星號組合還可以繼續匹配去掉末尾字符之后的s；

• 不匹配字符（可以是不能匹配，也可以是不“想匹配），將該字母 &星號組合扔掉，不再進行匹配

如果按照這個角度進行思考，我們可以寫出很精巧的狀態轉移方程：

3）在任意情況下，只要?p[j]?是字符?.，那么?p[j]?一定成功匹配?s?中的任意一個小寫字母。

?

最終的狀態轉移方程如下：

其中 matches(x,y) 判斷兩個字符是否匹配的輔助函數。只有當 y?是字符 . 或者 x 和 y 本身相同時，這兩個字符才會匹配。

class Solution:def isMatch(self, s: str, p: str) -> bool:m = len(s)n = len(p)def matches(i: int, j: int) -> bool:if i == 0:return False#0字符長度的s只和0字符長度的p匹配if p[j - 1] == '.':return True#字符.可以和任意一個字符匹配return s[i - 1] == p[j - 1]#兩個字符是否相等，相等即匹配'''注：這里的i和j表示s和p的前i位和前j位進行比較前i位和前j位字符串的最后一位，下標是i-1和j-1'''f = [[False] * (n + 1) for _ in range(m + 1)]f[0][0] = True#0字符長度的s只和0字符長度的p匹配for i in range(m + 1): #s的匹配長度從0開始討論（因為空串也可以和 c*這樣的相匹配）for j in range(1, n + 1): #p的匹配長度從1開始討論（因為長度為0的p串唯一匹配的內容就是長度為0的s串， #這個的f我們已經將其賦值為True了）if p[j - 1] == '*':if matches(i, j - 1):f[i][j] = f[i - 1][j] or f[i][j - 2]#對應最終狀態轉換方程的第三行else:f[i][j] = f[i][j - 2]#對應最終狀態轉換方程的第四行else:if matches(i, j):f[i][j] = f[i - 1][j - 1]#對應狀態轉換方程的第一行else:pass#對應狀態轉換方程的第二行return f[m][n]

舉例說明：s='aa',p='a*'

1)初始化：所有的f都是F(False)

?	s_0	s_1	s_2
p_0	T	F	F
p_1	F	F	F
p_2	F	F	F

?

2）i=0,j=1

0字符長度的s只和0字符長度的p匹配，所以f[0][1]=False

?	s_0	s_1	s_2
p_0	T	F	F
p_1	F	F	F
p_2	F	F	F

?

3) i=0 j=2

p[j-1]=p[1]='*'

那我們就先看 match(i,j-1)，即match(0,1)的值是否為真。

因為i==0，所以match(i,j-1)為False。

所以f[i][j]=f[i][j-2]，即f[0][2]=f[0][0]=True

?	s_0	s_1	s_2
p_0	T	F	T
p_1	F	F	F
p_2	F	F	F

?

4) i=1,j=1

p[j-1]=a≠’*‘，所以我們去看match(1,1)，即s[0]和p[0]的值。這兩個相等，所以match(1,1)為真。

所以f[i][j]=f[i-1][j-1]，即f[1][1]=f[0][0]=True

?	s_0	s_1	s_2
p_0	T	F	T
p_1	F	T	F
p_2	F	F	F

?

5）i=1,j=2

p[j-1]=p[1]='*'

那我們就先看 match(i,j-1)，即match(1,1)的值是否為真，即s[0]和p[0]的值是否相等。這兩個相等，所以match(1,1)為真。

所以f[i][j]=f[i][j-2] or f[i-1][j]，即f[1][2]=f[1][0] or f[0][2]=True

?	s_0	s_1	s_2
p_0	T	F	T
p_1	F	T	T
p_2	F	F	F

?

6) i=2,j=1

p[j-1]=a≠’*‘，所以我們去看match(2,1)，即s[1]和p[0]的值。這兩個相等，所以match(2,1)為真。

所以f[i][j]=f[i-1][j-1]，即f[2][1]=f[1][0]=False

?	s_0	s_1	s_2
p_0	T	F	T
p_1	F	T	T
p_2	F	F	F

?

7) i=2,j=2

p[j-1]=p[1]='*'

那我們就先看 match(i,j-1)，即match(2,1)的值是否為真，即s[1]和p[0]的值是否相等。這兩個相等，所以match(2,1)為真。

所以f[i][j]=f[i][j-2] or f[i-1][j]，即f[2][2]=f[2][0] or f[1][2]=True

?	s_0	s_1	s_2
p_0	T	F	T
p_1	F	T	T
p_2	F	F	T

?

這個也是最終的f矩陣圖了。

我們最終需要的是f[2][2]的真假，看圖可知為真。所以p可以匹配s

?

?

?

總結

以上是生活随笔為你收集整理的文巾解题 10. 正则表达式匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。