Dấu ngoặc đơn hợp lệ dài nhất trong Python

Giả sử chúng ta có một chuỗi, có mở và đóng ngoặc đơn. Chúng ta phải tìm độ dài dài nhất của các dấu ngoặc hợp lệ (đúng dạng). Vì vậy, nếu đầu vào là “)) (()) ())”, thì kết quả sẽ là 6, vì chuỗi hợp lệ là “(()) ()”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một ngăn xếp và chèn -1., Đặt ans:=0

• cho tôi trong phạm vi từ 0 đến chiều dài của ngăn xếp - 1

  • nếu s [i] đang mở ngoặc đơn, thì hãy chèn i vào ngăn xếp

  • nếu không thì

    • nếu ngăn xếp không trống và đỉnh ngăn xếp không phải -1 và s [đỉnh ngăn xếp] đang mở ngoặc đơn thì

      • phần tử trên cùng từ ngăn xếp

      • ans:=max of ans và i - stack top

    • nếu không thì chèn tôi vào ngăn xếp

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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("))(())())"))

Đầu vào

"))(())())"

Đầu ra

6