給你一個字符串 s 和一個字符規律 p，請你來實現一個支持 '.' 和 '*' 的正則表達式匹配。

'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋?整個?字符串?s的，而不是部分字符串。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/regular-expression-matching
?

例：

輸入：s = "aa", p = "a*"
輸出：true
解釋：因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重復了一次。

解析：

使用動態規劃dp數組，"."可以匹配任意字符，"*"可以和前一個字符匹配任意數目的相同字符。

class Solution(object):def isMatch(self, s, p):""":type s: str:type p: str:rtype: bool"""m, n = len(s), len(p) # 兩個字符長度dp = [[False] * (n + 1) for _ in range(m + 1)] # 初始化dp數組dp[0][0] = True # 沒有字符時可以匹配for j in range(1, n + 1): # 初始化第一行if p[j - 1] == '*': # "*"可以消除前一個字符，所以等于向前兩個字符的dp值dp[0][j] = dp[0][j - 2]else:dp[0][j] = Falsefor i in range(1, m + 1): # 遍歷dp數組for j in range(1, n + 1):if s[i - 1] == p[j - 1]: # 相同直接匹配dp[i][j] = dp[i - 1][j - 1]else:if p[j - 1] == '.': # 為"."時隨意匹配dp[i][j] = dp[i - 1][j - 1]elif p[j - 1] == '*': # 為"*"時的情況dp[i][j] = dp[i][j - 2] # 可以消除前一個字符，所以p字符串可以前跳兩格if s[i - 1] == p[j - 2] or p[j - 2] == '.': # 前一個字符可以匹配上的情況下，如果之前都能匹配的上，那么無論加上多少個相同字符，"*"都能匹配上dp[i][j] |= dp[i - 1][j] # 兩個情況滿足一個即可else:dp[i][j] = Falsereturn dp[m][n] # 返回dp數組最后一格即可

總結

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

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