Khớp biểu thức chính quy trong Python

Cho chuỗi s và pattern p. Hỗ trợ '.' (khớp 1 ký tự bất kỳ) và '*' (khớp 0 hoặc nhiều lần ký tự trước). Ví dụ: s="aa", p="a." -> true; s="aaaaaa", p="a*" -> true.

Các bước giải quyết (Dynamic Programming):

• dp[i][j] = true nếu s[:i] khớp p[:j]
• Khởi tạo dp[0][0] = true
• Xử lý '*' ở pattern: dp[0][i] = dp[0][i-2] nếu p[i]=='*'
• Điền bảng: nếu khớp ký tự hoặc '.' -> dp[i][j]=dp[i-1][j-1]; nếu '*' -> dp[i][j]=dp[i][j-2] hoặc (nếu khớp ký tự trước) dp[i][j]=dp[i][j] or dp[i-1][j]

Ví dụ

class Solution(object):
    def isMatch(self, s, p):
        ss = len(s)
        ps = len(p)
        dp = [[False for i in range(ps+1)] for j in range(ss+1)]
        p = " " + p
        s = " " + s
        dp[0][0] = True
        for i in range(2, ps+1):
            dp[0][i] = dp[0][i-2] if p[i]=='*' else False
        for i in range(1, ss+1):
            for j in range(1, ps+1):
                if s[i] == p[j] or p[j]=='.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j] == '*':
                    dp[i][j] = dp[i][j-2]
                    if s[i] == p[j-1] or p[j-1]=='.':
                        dp[i][j] = max(dp[i][j], dp[i-1][j])
        return dp[ss][ps]

ob = Solution()
print(ob.isMatch("aa", "a."))
print(ob.isMatch("aaaaaa", "a*"))

Đầu vào

"aa", "a." "aaaaaa", "a*"

Đầu ra

True True