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