পাইথনে বন্ধনী বৈধ করতে ন্যূনতম যোগ করুন

ধরুন আমাদের '(' এবং ')' বন্ধনীর একটি স্ট্রিং S আছে, আমরা যেকোনো অবস্থানে সর্বনিম্ন বন্ধনীর সংখ্যা যোগ করি, যাতে ফলস্বরূপ বন্ধনী স্ট্রিংটি বৈধ হয়। একটি বন্ধনী স্ট্রিং বৈধ যদি এবং শুধুমাত্র যদি −

• এটি খালি স্ট্রিং
• এটি XY (Y এর সাথে X সংযুক্ত) হিসাবে লেখা যেতে পারে, যেখানে X এবং Y বৈধ স্ট্রিং
• এটি (A) হিসাবে লেখা যেতে পারে, যেখানে A একটি বৈধ স্ট্রিং।

তাই যদি স্ট্রিংটি "()))((" এর মত হয়, তাহলে স্ট্রিংটিকে বৈধ করতে আমাদের আরও 4টি বন্ধনী যুক্ত করতে হবে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি S খালি হয়, তাহলে 0 ফেরত দিন
• count :=0, temp হল একটি অ্যারে, temp_counter :=0
• আমি S
  তে
  • যদি আমি বন্ধনী খুলছি, তাহলে টেম্পে i ঢোকান
  • অন্যথায়
    • যখন temp এর দৈর্ঘ্য> 0 এবং এর শেষ উপাদানটি বন্ধনী খুলছে, তখন temp-এর শেষ উপাদানটি মুছে দিন, অন্যথায় temp-এ 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