পাইথনে দীর্ঘতম বৈধ বন্ধনী

ধরুন আমাদের একটি স্ট্রিং আছে, খোলা ও বন্ধ বন্ধনী সহ। আমাদের বৈধ (সুগঠিত) বন্ধনীর দীর্ঘতম দৈর্ঘ্য খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি “))(())()”” এর মত হয়, তাহলে ফলাফল হবে 6, কারণ বৈধ স্ট্রিং হল “(())()”।

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

• একটি স্ট্যাক তৈরি করুন এবং সন্নিবেশ করুন -1., উত্তর সেট করুন :=0

• 0 থেকে স্ট্যাকের দৈর্ঘ্য - 1

  এর মধ্যে i এর জন্য

  • যদি s[i] বন্ধনী খুলছে, তাহলে i ঢোকান স্ট্যাকের মধ্যে

  • অন্যথায়

    • যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের শীর্ষ -1 না হয় এবং s[স্ট্যাক টপ] বন্ধনী খুলছে, তাহলে

      • স্ট্যাক থেকে শীর্ষ উপাদান

      • উত্তর :=সর্বোচ্চ উত্তর এবং i – স্ট্যাক টপ

    • অন্যথায় আমি স্ট্যাকের মধ্যে ঢোকান

• উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

class Solution(object):
   def longestValidParentheses(self, s):
      stack = [-1]
      ans = 0
      for i in range(len(s)):
         if s[i] == "(":
            stack.append(i)
         else:
            if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
               stack.pop()
               ans = max(ans,i - stack[-1])
            else:
            stack.append(i)
      return ans
ob = Solution()
print(ob.longestValidParentheses("))(())())"))

ইনপুট

"))(())())"

আউটপুট

6