मान लीजिए कि हमारे पास एक इनपुट स्ट्रिंग s और दूसरी इनपुट स्ट्रिंग p है। यहाँ मुख्य स्ट्रिंग है और p पैटर्न है। हमें एक विधि को परिभाषित करना होगा, जो स्ट्रिंग में पैटर्न से मेल खा सके। इसलिए हमें इसे रेगुलर एक्सप्रेशन के लिए लागू करना होगा, जो '?' और '*' जैसे वाइल्डकार्ड वर्णों का समर्थन करता है।
-
डॉट '?' किसी एक वर्ण से मेल खाता है
-
स्टार '*' शून्य या अधिक वर्णों से मेल खाता है।
तो उदाहरण के लिए, यदि इनपुट s ="aa" और p ="a?" जैसा है, तो यह सही होगा, उसी इनपुट स्ट्रिंग के लिए, यदि पटर "? *" है, तो यह सत्य होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
ss:=s और ps का आकार:=p का आकार
-
dp को ss x ps आकार का एक मैट्रिक्स बनाएं, और इसे गलत मान का उपयोग करके भरें
-
इनके पहले एक खाली जगह जोड़कर p और s को अपडेट करें
-
1 से ps की श्रेणी में i के लिए -
-
अगर p[i] =तारा, तो
-
डीपी [0, आई]:=डीपी [0, आई -1]
-
-
-
मेरे लिए 1 से ss की सीमा में
-
j के लिए 1 से ps की सीमा में
-
अगर s[i] p[j] है, या p[j] '?' है, तो
-
डीपी [आई, जे]:=डीपी [i - 1, जे - 1]
-
-
अन्यथा जब p[j] तारा है, तब
-
dp[i, j] :=अधिकतम dp[i-1, j] और dp[i, j-1]
-
-
-
-
वापसी डीपी [एसएस, पीएस]
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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