पायथन में रेगुलर एक्सप्रेशन पैटर्न स्ट्रिंग से मेल खाता है या नहीं जांचने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s और एक रेगुलर एक्सप्रेशन पैटर्न है। हमें जांचना है कि दिया गया पैटर्न दी गई स्ट्रिंग से मेल खाता है या नहीं। रेगुलर एक्सप्रेशन में कुछ नियम हैं:

• . (पीरियड) किसी भी एकल वर्ण से मेल खाता है
• * (एस्टरिस्क) पूर्ववर्ती तत्व के शून्य या अधिक घटनाओं से मेल खाता है

उदाहरण के लिए, यदि इनपुट है pattern = "h.l*o", s = "hello", तो आउटपुट True होगा।

एल्गोरिदम (डायनामिक प्रोग्रामिंग के साथ रिकर्सन)

• n := s का आकार, m := p का आकार
• dp(i, j) फ़ंक्शन परिभाषित करें:
  • यदि j == m, तो i == n वापस करें
  • match := (i < n और (s[i] == p[j] या p[j] == "."))
  • यदि j+1 < m और p[j+1] == "*", तो dp(i, j+2) या (match और dp(i+1, j)) वापस करें
  • अन्यथा match और dp(i+1, j+1) वापस करें
• मुख्य विधि से dp(0, 0) वापस करें

उदाहरण

class Solution:
    def solve(self, p, s):
        n = len(s)
        m = len(p)
        def dp(i, j):
            if j == m: return i == n
            match = i < n and (s[i] == p[j] or p[j] == ".")
            if j + 1 < m and p[j + 1] == "*":
                return dp(i, j + 2) or (match and dp(i + 1, j))
            return match and dp(i + 1, j + 1)
        return dp(0, 0)

ob = Solution()
pattern = "h.l*o"
s = "hello"
print(ob.solve(pattern, s))

इनपुट

"h.l*o", "hello"

आउटपुट

True