ধরুন একটি ইনপুট স্ট্রিং s এবং অন্য একটি ইনপুট স্ট্রিং p। s হল মূল স্ট্রিং এবং p হল প্যাটার্ন। আমাদের একটি মেথড সংজ্ঞায়িত করতে হবে যা প্যাটার্নটি স্ট্রিংএ ম্যাচ করতে পারে। régুলার এক্সপ্রেশন ইমপ্লিমেন্ট করতে হবে যা '?' এবং '*' 와일্ডকার্ড সাপোর্ট করে।
- '?' যেকোনো একক ক্যারেক্টার ম্যাচ করে
- '*' শূন্য বা অধিক ক্যারেক্টার ম্যাচ করে
উদাহরণ: s = "aa" এবং p = "a?" হলে true, p = "?*" হলে true।
সমাধানের ধাপগুলো −
- sl := len(s), pl := len(p)
- dp ম্যাট্রিক্স তৈরি করুন sl x pl আকারের, false দিয়ে ভরুন
- p এবং s-এর আগে একটি ব্ল্যাঙ্ক স্পেস যোগ করুন
- i = 1 থেকে pl পর্যন্ত − যদি p[i] == '*' হয় তবে dp[0][i] = dp[0][i-1]
- i = 1 থেকে sl পর্যন্ত, j = 1 থেকে pl পর্যন্ত − যদি s[i]==p[j] অথবা p[j]=='?' হলে dp[i][j] = dp[i-1][j-1]; অন্যথায় যদি p[j]=='*' হলে dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- dp[sl][pl] রিটার্ন করুন
উদাহরণ (পাইথন)
নিচের ইমপ্লিমেন্টেশনটি দেখুন −
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
