Chương trình tìm độ dài của dấu ngoặc hợp lệ dài nhất từ ​​chuỗi đã cho bằng Python

Giả sử chúng ta có một chuỗi s. Dấu này chỉ bao gồm dấu ngoặc đơn mở và đóng ngoặc đơn. Chúng ta phải tìm độ dài của chuỗi con trong dấu ngoặc đơn hợp lệ (được hình thành tốt) dài nhất. 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 solve(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.solve("))(())())"))

Đầu vào

"))(())())"

Đầu ra

6