পাইথনে রেগুলার এক্সপ্রেশন প্যাটার্ন স্ট্রিংয়ের সাথে মিলে যাচ্ছে কিনা তা যাচাই করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s এবং একটি রেগুলার এক্সপ্রেশন প্যাটার্ন p দেওয়া আছে। আমাদের যাচাই করতে হবে যে দেওয়া প্যাটার্নটি স্ট্রিংয়ের সাথে মিলে যাচ্ছে কিনা। রেগুলার এক্সপ্রেশনে নিচের নিয়মগুলো প্রযোজ্য:

• . (পিরিয়ড) — যেকোনো একক ক্যারেক্টার সাথে মিলে
• * (এস্টারিস্ক) — পূর্ববর্তী এলিমেন্টের শূন্য বা অধিক বার повторнение মিলে

উদাহরণস্বরূপ, ইনপুট pattern = "h.l*o", s = "hello" হলে আউটপুট হবে True, কারণ h এর পর যেকোনো একটা ক্যারেক্টার (e), তারপর l শূন্য বা অধিকবার (ll), এবং শেষে o।

সমাধানের ধাপসমূহ

• n := len(s), m := len(p)
• dp(i, j) ফাংশন সংজ্ঞায়িত করুন:
  • যদি j == m, তবে i == n ফেরত দিন
  • match := (i < n and (s[i] == p[j] or p[j] == "."))
  • যদি j + 1 < m and p[j+1] == "*", তবে ফেরত দিন dp(i, j+2) or (match and dp(i+1, j))
  • ফেরত দিন match and dp(i+1, j+1)
• মূল পদ্ধতিতে dp(0, 0) ফেরত দিন

উদাহরণ

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))

ইনপুট

"h.l*o", "hello"

আউটপুট

True