Chương trình kiểm tra mẫu biểu thức chính quy có khớp với chuỗi hay không trong Python

Giả sử chúng ta có một chuỗi s và một mẫu biểu thức chính quy. Chúng ta phải kiểm tra xem mẫu đã cho có khớp với chuỗi đã cho hay không. Trong biểu thức chính quy, có một số quy tắc -

• . (dấu chấm) khớp với bất kỳ ký tự đơn nào

• * (dấu hoa thị) khớp với không hoặc nhiều hơn phần tử trước đó.

Vì vậy, nếu đầu vào giống như pattern ="h.l * o" s ="hello", thì đầu ra sẽ là True, vì Chúng ta có ra và sau đó là một ký tự duy nhất

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s

• m:=kích thước của p

• Định nghĩa một hàm dp (). Điều này sẽ mất tôi, j

• nếu j giống với m thì

  • trở lại tôi cũng giống như n

• match:=true khi (i

• nếu j + 1 &m và p [j + 1] giống như "*" thì

  • trả về true khi dp (i, j + 2) hoặc (match và dp (i + 1, j)) nếu không thì false

• đối sánh trả về và dp (i + 1, j + 1)

• Từ phương thức chính trả về dp (0, 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution:
   def solve(self, p, s):
      n = len(s)
      m = len(p)
      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))

Đầu vào

"h.l*o", "hello"

Đầu ra

True