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

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

• '.' যেকোনো একক ক্যারেক্টার ম্যাচ করে
• '*' পূর্ববর্তী এলিমেন্টের শূন্য বা অধিকবার ম্যাচ করে

উদাহরণ: s = "aa" এবং p = "a." হলে true, p = ".*" হলে true।

সমাধানের ধাপগুলো −

• ss := len(s), ps := len(p)
• dp ম্যাট্রিক্স তৈরি করুন ss x ps আকারের, false দিয়ে ভরুন
• p এবং s-এর আগে একটি ব্ল্যাঙ্ক স্পেস যোগ করুন
• i = 2 থেকে ps পর্যন্ত − dp[0][i] = dp[0][i-2] যদি p[i]=='*' অন্যথায় False
• i = 1 থেকে ss পর্যন্ত, j = 1 থেকে ps পর্যন্ত − যদি 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] = max(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