Dãy ngoặc hợp lệ dài nhất trong Python

Cho chuỗi chứa dấu ngoặc mở và đóng. Tìm độ dài dãy ngoặc hợp lệ (well-formed) dài nhất. Ví dụ: "))(())())" -> 6 (dãy "(())()").

Các bước giải quyết (Stack O(n)):

• Stack khởi tạo [-1], ans = 0
• Duyệt i: nếu '(' thì push i; nếu ')' thì pop, nếu stack không rỗng thì ans = max(ans, i - stack[-1]), ngược lại push i

Ví dụ

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