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