下面使用動态規劃來實現簡單的正則表達式匹配。題目如下：

假設？可以匹配任意的一個字符，*可以匹配0到任意個字符，正則表達式隻能由數字，英文字母、？和*組成，字符串由英文字母和數字組成，編寫一個程序，給定一個滿足上述規則的正則表達式和字符串，返回正則表達式是否匹配該字符串。

以下是匹配的例子：

下面看看代碼如何寫。

用pattern = "hel?o"和 sentence = "hello"進行嘗試：

發現pattern[0] = sentence[0]，則i和j分别 1，繼續判斷，直到i=3和j=3，如下圖所示：

此時pattern[3] != sentence[3]，但由于pattern[i]此時的值為?,可以匹配任意一個字符，因此認為仍然匹配，i和j分别 1，繼續往下匹配。

定義表達式dp(i,j)為pattern[i:]和sentence[j:]是否匹配。從上述分析可以看出，如果

pattern[i] == sentence[j] 或者 sentence[j] == "?"，則 dp[i][j] = dp[i 1][j 1]。

主要的困難在于*的處理。假設pattern="***bc",sentence="abc",那麼，對于第一個*号，可以有以下4種情形：

情形1：不匹配任何字符

情形2：匹配第一個字符

情形3：匹配前二個字符：

情形4：匹配前三個字符：

經過上述分析，可以得出結論：

dp[i][j] = U(dp[i 1][k])， k=j....N。 其中隻要有任意一個dp[i 1][k]為True，則

dp[i][j] = True

代碼編寫如下：

def simple_regex(mod,s,i,j): if i<len(mod) and j<len(s) and (mod[i] == s[j] or mod[i] == "?"): return simple_regex(mod,s,i 1,j 1) elif i == len(mod): return j == len(s) elif mod[i] == "*": for k in range(j,len(s) 1): if simple_regex(mod,s,i 1,k): return True return False print(simple_regex("a*b*c*d****e","athis is a boy and cow and welcome",0,0)) print(simple_regex( "*p*","help",0,0)) print(simple_regex( "*p*","papa",0,0)) print(simple_regex( "*p*","a",0,0)) print(simple_regex( "*p*","p",0,0)) print(simple_regex("he?p","p",0,0)) print(simple_regex("he?p","help",0,0)) print(simple_regex("he?p","heap",0,0)) print(simple_regex("he?p","healp",0,0)) print(simple_regex("*bb*","babbbc",0,0)) print(simple_regex("*bb*p","babbbc",0,0)) print(simple_regex("*bb*","babbbc",0,0)) print(simple_regex("***bb*","b",0,0))

程序輸出：

True True True False True False True True False True False True False

按照動态規劃的思路，增加緩存，同時将

for k in range(j,len(s) 1): if simple_regex(mod,s,i 1,k):

替換成遞歸的實現以提升效率，代碼如下：

pattern ="t*b*c*d****e" sentence = "this is a boy and cow and welcome" cache = [[-1 for i in range(len(sentence) 1)] for j in range(len(pattern) 1)] def simple_regex(mod,s,i,j): if not (cache[i][j] == -1): return cache[i][j] cache[i][j] = False if i<len(mod) and j<len(s) and (mod[i] == s[j] or mod[i] == "?"): cache[i][j] =simple_regex(mod,s,i 1,j 1) elif i == len(mod): cache[i][j] = j == len(s) elif mod[i] == "*": cache[i][j] = simple_regex(mod,s,i 1,j) or (j<len(s) 1 and simple_regex(mod,s,i,j 1)) return cache[i][j] print(wild_char(pattern,sentence,0,0))

解釋下上述代碼。

第13行，當mod[i]==‘*’時，我們将循環寫成了遞歸形式。simple_regex(mod,s,i 1,j)表示*号不匹配任何字符。simple_regex(mod,s,i,j 1)表示*号匹配一個字符後，進入下一次遞歸調用。通過這兩個遞歸組合就完成了

for k in range(j,len(s) 1): if simple_regex(mod,s,i 1,k):

達到的效果。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!