Chương trình kiểm tra khớp mẫu regex với chuỗi trong Python

Cho chuỗi s và mẫu regex p. Kiểm tra xem mẫu có khớp với toàn bộ chuỗi hay không. Quy tắc regex:

• . (chấm) khớp với bất kỳ ký tự đơn nào.
• * (sao) khớp với 0 hoặc nhiều lần ký tự ngay trước nó.

Ví dụ: pattern = "h.l*o", s = "hello" → True (khớp: h, e, ll, o).

Giải thuật (Đệ quy + Memoization / DP)

Hàm dp(i, j) trả về True nếu s[i:] khớp với p[j:].

• Nếu j == len(p): trả về i == len(s).
• match = i < len(s) and (s[i] == p[j] or p[j] == '.').
• Nếu j+1 < len(p) và p[j+1] == '*':
  • Bỏ qua x*: dp(i, j+2).
  • Hoặc dùng * khớp thêm ký tự: match and dp(i+1, j).
• Ngược lại: match and dp(i+1, j+1).

Ví dụ minh họa

class Solution:
    def solve(self, p, s):
        n, m = len(s), len(p)
        from functools import lru_cache
        
        @lru_cache(None)
        def dp(i, j):
            if j == m:
                return i == n
            match = i < n and (s[i] == p[j] or p[j] == '.')
            if j + 1 < m and p[j+1] == '*':
                return dp(i, j+2) or (match and dp(i+1, j))
            return match and dp(i+1, j+1)
        
        return dp(0, 0)

ob = Solution()
pattern = "h.l*o"
s = "hello"
print(ob.solve(pattern, s))  # Output: True

Đầu vào / Đầu ra

Input: "h.l*o", "hello"

Output: True