पायथन में नियमित अभिव्यक्ति मिलान

मान लीजिए कि हमारे पास एक इनपुट स्ट्रिंग s और दूसरी इनपुट स्ट्रिंग p है। यहाँ s मुख्य स्ट्रिंग है और p पैटर्न है। हमें एक विधि को परिभाषित करना होगा, जो स्ट्रिंग में पैटर्न से मेल खा सके। इसलिए हमें इसे रेगुलर एक्सप्रेशन के लिए लागू करना होगा, जो '.' और '*' का समर्थन करता है।

• डॉट '।' किसी एक वर्ण से मेल खाता है

• स्टार '*' पिछले तत्व के शून्य या अधिक से मेल खाता है।

तो उदाहरण के लिए, यदि इनपुट s ="aa" और p ="a" जैसा है, तो यह सही होगा, उसी इनपुट स्ट्रिंग के लिए, यदि पैटर ".*" है, तो यह सत्य होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ss:=s और ps का आकार:=p का आकार

• dp को ss x ps आकार का एक मैट्रिक्स बनाएं, और इसे गलत मान का उपयोग करके भरें

• इनके पहले एक खाली जगह जोड़कर p और s को अपडेट करें

• 2 से ps की श्रेणी में i के लिए -

  • dp[0, i] :=dp[0, i - 2] जब p[i] तारा हो, अन्यथा असत्य

• मेरे लिए 1 से ss की सीमा में

  • j के लिए 1 से ps की सीमा में

    • अगर s[i] p[j] है, या p[j] डॉट है, तो

      • डीपी [आई, जे]:=डीपी [i - 1, जे - 1]

    • अन्यथा जब p[j] तारा है, तब

      • डीपी [आई, जे]:=डीपी [आई, जे -2]

      • अगर s[i] p[j – 1] है या p[j – 1] डॉट है, तो

        • dp[i, j] :=अधिकतम dp[i, j] और dp[i – 1, j]

• वापसी डीपी [एसएस, पीएस]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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