পাইথনে নিয়মিত এক্সপ্রেশন ম্যাচিং

ধরুন আমাদের একটি ইনপুট স্ট্রিং s এবং আরেকটি ইনপুট স্ট্রিং p আছে। এখানে s হল প্রধান স্ট্রিং এবং p হল প্যাটার্ন। আমরা একটি পদ্ধতি সংজ্ঞায়িত করতে হবে, যে স্ট্রিং মধ্যে নিদর্শন মিলতে পারে. তাই আমাদের এটিকে একটি রেগুলার এক্সপ্রেশনের জন্য বাস্তবায়ন করতে হবে, যা '.' এবং '*' সমর্থন করে।

• ডট ‘.’ যেকোন একক অক্ষরের সাথে মেলে

• তারা '*' পূর্ববর্তী উপাদানের সাথে শূন্য বা তার বেশি মেলে।

সুতরাং উদাহরণস্বরূপ, যদি ইনপুটটি s =“aa” এবং p =“a” এর মত হয়, তবে এটি সত্য হবে, একই ইনপুট স্ট্রিংয়ের জন্য, যদি প্যাটারটি “.*” হয়, তবে এটি সত্য হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ss :=s এর আকার এবং ps :=p এর আকার

• dp আকার ss x ps এর একটি ম্যাট্রিক্স তৈরি করুন এবং মিথ্যা মান ব্যবহার করে এটি পূরণ করুন

• এর আগে একটি ফাঁকা স্থান যোগ করে p এবং s আপডেট করুন

• আমি 2 থেকে ps −

  পরিসরে

  • dp[0, i] :=dp[0, i - 2] যখন p[i] তারকা হয়, অন্যথায় মিথ্যা

• আমি রেঞ্জ 1 থেকে ss

  এর জন্য

  • 1 থেকে ps

    রেঞ্জের মধ্যে j-এর জন্য

    • যদি s[i] হয় p[j], অথবা p[j] বিন্দু হয়, তাহলে

      • dp[i, j] :=dp[i – 1, j – 1]

    • অন্যথায় যখন p[j] তারকা হয়, তখন

      • dp[i, j] :=dp[i, j - 2]

      • যদি s[i] হয় p[j – 1] অথবা p[j – 1] বিন্দু হয়, তাহলে

        • dp[i, j] :=dp[i, j] এবং dp[i – 1, j]

          এর সর্বোচ্চ

• dp[ss, ps]

  ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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

ইনপুট

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

আউটপুট

True
True