?LeetCode刷題實(shí)戰(zhàn)10：字符串正則匹配

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問(wèn)題叫做正則表達(dá)式匹配，我們先來(lái)看題面：

Given an input string (s) and a pattern (p), implement regular expression
matching with support for?'.'?and?'*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the?entire?input string (not partial).

https://leetcode.com/problems/regular-expression-matching/

Note:

• s?could be empty and contains only lowercase letters?a-z.
• p?could be empty and contains only lowercase letters?a-z, and characters like?.?or?*.

題意

這道題屬于典型的人狠話不多的問(wèn)題，讓我們動(dòng)手實(shí)現(xiàn)一個(gè)簡(jiǎn)單的正則匹配算法。不過(guò)為了降低難度，這里需要匹配的只有兩個(gè)特殊符號(hào)，一個(gè)符號(hào)是'.'，表示可以匹配任意的單個(gè)字符。還有一個(gè)特殊符號(hào)是'*'，它表示它前面的符號(hào)可以是任意個(gè)，可以是0個(gè)。

題目要求是輸入一個(gè)母串和一個(gè)模式串，請(qǐng)問(wèn)是否能夠達(dá)成匹配。

這題要求的是完全匹配，而不是包含匹配。也就是說(shuō)s串匹配完p串之后不能有剩余，比如剛好完全匹配才行。明確了這點(diǎn)之后，我們先來(lái)簡(jiǎn)化操作，假設(shè)不存在'*'這個(gè)特殊字符，只存在'.'，那么顯然，這個(gè)簡(jiǎn)化過(guò)后的問(wèn)題非常簡(jiǎn)單，我們隨便就可以寫出代碼：

def match(s, p):  n = len(s)  for i in range(n):    if s[i] == p[i] or p[i] == '.':      continue    return False  return True

我們下面考慮加入'*'的情況，其實(shí)加入'*'只會(huì)有一個(gè)問(wèn)題，就是'*'可以匹配任意長(zhǎng)度，如果當(dāng)前位置出現(xiàn)了'*'，我們并不知道它應(yīng)該匹配到哪里為止。我們不知道需要匹配到哪里為止，那么就需要進(jìn)行搜索了。也就是說(shuō)，我們需要將它轉(zhuǎn)換成一個(gè)搜索問(wèn)題來(lái)進(jìn)行求解。我們?cè)囍眠f歸來(lái)寫一下：

def match(s, p, i, j):    # 當(dāng)前位置是否匹配    flag = s[i] == p[j] or p[j] == '.'    # 判斷p[j+1]是否是*，如果是那么說(shuō)明p[j]可以跳過(guò)匹配    if j+1 < len(p) and p[j+1] == '*':        # 兩種情況，一種是跳過(guò)p[j]，另一種是p[j]繼續(xù)匹配        return match(s, p, i, j+2) or (flag and match(s, p, i+1, j))    else:        # 如果沒(méi)有*，只有一種可能        return flag and match(s, p, i+1, j+1)

memory = {}def match(s, p, i, j):    if (i, j) in memory:      return memory[(i, j)]    # 當(dāng)前位置是否匹配    flag = s[i] == p[j] or p[j] == '.'    # 判斷p[j+1]是否是*，如果是那么說(shuō)明p[j]可以跳過(guò)匹配    if j+1 < len(p) and p[j+1] == '*':        # 兩種情況，一種是跳過(guò)p[j]，另一種是p[j]繼續(xù)匹配        ret = match(s, p, i, j+2) or (flag and match(s, p, i+1, j))    else:        # 如果沒(méi)有*，只有一種可能        ret = flag and match(s, p, i+1, j+1)    memory[(i, j)] = ret    return ret

如果你對(duì)動(dòng)態(tài)規(guī)劃足夠熟悉的話，想必也應(yīng)該知道，記憶化搜索本質(zhì)也是動(dòng)態(tài)規(guī)劃的一種實(shí)現(xiàn)方式。但同樣，我們也可以選擇其他的方式實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃，就可以擺脫遞歸了，相比于遞歸，使用數(shù)組存儲(chǔ)狀態(tài)的遞推形式更容易理解。

我們用dp[i][j]存儲(chǔ)s[:i]與p[:j]是否匹配，那么根據(jù)我們之前的結(jié)論，如果p[j-1]是'*'，那么dp[i][j]可能由dp[i][j-2]或者是dp[i-1][j]轉(zhuǎn)移得到。dp[i][j-2]比較容易想到，就是'*'前面的字符作廢，為什么是dp[i-1][j]呢？這種情況是代表'*'連續(xù)匹配，因?yàn)榭赡芷ヅ淙我鈧€(gè)，所以必須要匹配在'*'這個(gè)位置。

舉個(gè)例子：

s = 'aaaaa'
p = '.*'

在上面這個(gè)例子里，'.'能匹配所有字符，但是問(wèn)題是s中只有一個(gè)a能匹配上。如果我們不用dp[i-1][j]而用dp[i-1][j-1]的話，那么是無(wú)法匹配aa或者aaa這種情況的。因?yàn)檫@幾種情況都是通過(guò)'*'的多匹配能力實(shí)現(xiàn)的。如果還不理解的同學(xué)， 建議仔細(xì)梳理一下它們之間的關(guān)系。

我們用數(shù)組的形式寫出代碼：

def is_match(s, p):    # 為了防止超界，我們從下標(biāo)1開(kāi)始    s = '$' + s    p = '$' + p    n, m = len(s), len(p)    dp = [[False for _ in range(m)] for _ in range(n)]
    dp[0][0] = True
    # 需要考慮s空串匹配的情況    for i in range(n):        for j in range(1, m):            # 標(biāo)記當(dāng)前位置是否匹配，主要考慮s為空串的情況            match = True if i > 0 and (s[i] == p[j] or p[j] == '.') else False            # 判斷j位置是否為'*'            if j > 1 and p[j] == '*':                # 如果是，只有兩種轉(zhuǎn)移的情況，第一種表示略過(guò)前一個(gè)字符，第二種表示重復(fù)匹配                dp[i][j] = dp[i][j-2] or ((s[i] == p[j-1] or p[j-1] == '.') and dp[i-1][j])            else:                # 如果不是，只有一種轉(zhuǎn)移的可能                dp[i][j] = dp[i-1][j-1] and match    return dp[n-1][m-1]