पायथन में पैरेंथेसिस को वैध बनाने के लिए न्यूनतम जोड़

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

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

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

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

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

उदाहरण

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