पायथन में कोष्ठकों को मान्य बनाने के लिए न्यूनतम जोड़ें

मान लीजिए कि हमारे पास '(' और ')' कोष्ठकों का एक स्ट्रिंग S है, हम किसी भी स्थिति में कोष्ठकों की न्यूनतम संख्या जोड़ते हैं, ताकि परिणामी कोष्ठक स्ट्रिंग मान्य हो। एक कोष्ठक स्ट्रिंग मान्य है यदि और केवल यदि -

• यह खाली स्ट्रिंग है
• इसे XY के रूप में लिखा जा सकता है (X को Y के साथ जोड़ा जाता है), जहां X और Y मान्य स्ट्रिंग हैं
• इसे (ए) के रूप में लिखा जा सकता है, जहां ए एक वैध स्ट्रिंग है।

इसलिए यदि स्ट्रिंग "()))((" की तरह है, तो हमें स्ट्रिंग को वैध बनाने के लिए 4 और कोष्ठक जोड़ने होंगे।

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

• अगर S खाली है, तो 0 वापस करें
• गिनती:=0, अस्थायी एक सरणी है, temp_counter:=0
• एस में मैं के लिए
  • अगर मैं कोष्ठक खोल रहा हूँ, तो i को अस्थायी में डालें
  • अन्यथा
    • जब अस्थायी की लंबाई> 0 और का अंतिम तत्व कोष्ठक खोल रहा है, तो अस्थायी के अंतिम तत्व को हटा दें, अन्यथा i को अस्थायी में डालें
• अस्थायी का आकार लौटाएं।

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

उदाहरण

class Solution:
   def minAddToMakeValid(self, S):
      if not S:
         return 0
      count = 0
      temp = []
      temp_counter = 0
      for i in S:
         if i =='(':
            temp.append(i)
         else:
            if len(temp)>0 and temp[len(temp)-1] =='(':
               temp.pop(len(temp)-1)
            else:
               temp.append(i)
      return len(temp)
ob = Solution()
print(ob.minAddToMakeValid("()))(("))

इनपुट

"()))(("

आउटपुट

4