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

題目描述

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

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

示例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無(wú)法匹配 "aa" 整個(gè)字符串。
示例 2:

輸入:
s = "aa"
p = "a"
輸出: true
解釋: 因?yàn)?'' 代表可以匹配零個(gè)或多個(gè)前面的那一個(gè)元素, 在這里前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次。
示例 3:

輸入:
s = "ab"
p = "."
輸出: true
解釋: "." 表示可匹配零個(gè)或多個(gè)（'*'）任意字符（'.'）。
示例 4:

輸入:
s = "aab"
p = "cab"
輸出: true
解釋: 因?yàn)?'*' 表示零個(gè)或多個(gè)，這里 'c' 為 0 個(gè), 'a' 被重復(fù)一次。因此可以匹配字符串 "aab"。
示例 5:

輸入:
s = "mississippi"
p = "misisp*."
輸出: false
s 可能為空，且只包含從 a-z 的小寫(xiě)字母。
p 可能為空，且只包含從 a-z 的小寫(xiě)字母以及字符 . 和 ，無(wú)連續(xù)的 ''。

解題思路

法1

使用動(dòng)態(tài)規(guī)劃來(lái)解決問(wèn)題。

最后的整個(gè)字符串是否匹配取決于前面的字符串是否匹配,并且最后一個(gè)字符是否匹配,如果前面的字符串都匹配,并且最后一個(gè)字符串也匹配,那么就匹配成功,否則就失敗

我們可以使用動(dòng)態(tài)規(guī)劃來(lái)獲取前一個(gè)的匹配狀態(tài),

具體來(lái)說(shuō)，我們使用一個(gè)二維數(shù)組 dp 來(lái)記錄已經(jīng)匹配的字符串和模式的狀態(tài)。其中 dp[i][j] 表示字符串的前 i 個(gè)字符和模式的前 j 個(gè)字符是否匹配。

初始狀態(tài)是 dp[0][0] = true，表示空字符串和空模式是匹配的。接下來(lái)，我們需要考慮一些特殊情況。

1. 將*與其前面的字符看成一個(gè)整體

如果模式的第一個(gè)字符是 *，則我們可以將其和它前面的字符視為一個(gè)整體，表示這個(gè)字符可以出現(xiàn) 0 次。因此，我們有 dp[0][j] = dp[0][j-2]，表示空字符串和模式的前 j 個(gè)字符是否匹配。

接下來(lái)，我們通過(guò)兩個(gè)循環(huán)來(lái)遍歷字符串和模式的所有子串。如果當(dāng)前的字符匹配，即 s[i-1] == p[j-1] 或者 p[j-1] == '.'，那么我們可以將 dp[i][j] 設(shè)置為 dp[i-1][j-1]，表示當(dāng)前的子串匹配情況和之前的子串匹配情況相同。如果當(dāng)前的模式字符是 *，我們需要考慮兩種情況。一種是當(dāng)前的字符可以出現(xiàn) 0 次，即 dp[i][j] = dp[i][j-2]。另一種是當(dāng)前的字符可以出現(xiàn)多次，即 dp[i][j] = dp[i-1][j]，這里需要注意的是，當(dāng)前的字符必須和前面的字符相同，或者前面的字符是 .。

最終，我們返回 dp[m][n]，表示整個(gè)字符串和模式是否匹配。其中 m 和 `

• 時(shí)間復(fù)雜度(O(nm))
• 空間復(fù)雜度(O(nm))

執(zhí)行結(jié)果

法1

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]bool, n+1)
    }
    dp[0][0] = true
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s[i-1] == p[j-1] || p[j-1] == '.' {
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' {
                if s[i-1] == p[j-2] || p[j-2] == '.' {
                    dp[i][j] = dp[i][j-2] || dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-2]
                }
            }
        }
    }
    return dp[m][n]
}

執(zhí)行結(jié)果：
通過(guò)
顯示詳情
查看示例代碼
添加備注

執(zhí)行用時(shí)：
0 ms
, 在所有 Go 提交中擊敗了
100.00%
的用戶
內(nèi)存消耗：
2.2 MB
, 在所有 Go 提交中擊敗了
79.37%
的用戶
通過(guò)測(cè)試用例：
448 / 448
炫耀一下:

法2

法3

本文由mdnice多平臺(tái)發(fā)布