পাইথনে ওয়াইল্ডকার্ড ম্যাচিং

ধরুন আমাদের একটি ইনপুট স্ট্রিং s এবং আরেকটি ইনপুট স্ট্রিং p আছে। এখানে প্রধান স্ট্রিং এবং p হল প্যাটার্ন। আমাদের একটি পদ্ধতি সংজ্ঞায়িত করতে হবে, যেটি স্ট্রিং এর প্যাটার্নের সাথে মেলে। তাই আমাদের একটি নিয়মিত অভিব্যক্তির জন্য এটি বাস্তবায়ন করতে হবে, যা '?' এবং '*' এর মতো ওয়াইল্ডকার্ড অক্ষর সমর্থন করে।

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

• তারকা ‘*’ শূন্য বা তার বেশি অক্ষর মেলে।

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

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

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

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

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

• আমি 1 থেকে ps −

  রেঞ্জের জন্য

  • যদি p[i] =তারকা, তাহলে

    • dp[0, i] :=dp[0, i - 1]

• আমি রেঞ্জ 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 – 1, j] এবং dp[i, j – 1]

• dp[ss, ps]

  ফেরত দিন

উদাহরণ (পাইথন)

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

class Solution(object):
   def isMatch(self, s, p):
      sl = len(s)
      pl = len(p)
      dp = [[False for i in range(pl+1)] for j in range(sl+1)]
      s = " "+s
      p = " "+p
      dp[0][0]=True
      for i in range(1,pl+1):
         if p[i] == '*':
            dp[0][i] = dp[0][i-1]
      for i in range(1,sl+1):
         for j in range(1,pl+1):
            if s[i] == p[j] or p[j] == '?':
               dp[i][j] = dp[i-1][j-1]
            elif p[j]=='*':
               dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      return dp[sl][pl]
ob = Solution()
print(ob.isMatch("aa", "a?"))
print(ob.isMatch("aaaaaa", "a*"))

ইনপুট

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

আউটপুট

True
True