Mô phỏng thuật toán Dấu ngoặc hợp lệ

Valid Parentheses · Nhóm: Ngăn xếp & Hàng đợi

Kiểm tra một chuỗi dấu ngoặc có hợp lệ không bằng ngăn xếp khớp cặp mở và đóng.

Ý tưởng

Gặp ngoặc mở thì đẩy nó vào ngăn xếp.

Gặp ngoặc đóng thì lấy đỉnh ngăn xếp ra và kiểm tra có đúng cặp không.

Duyệt hết chuỗi, nếu ngăn xếp rỗng nghĩa là mọi cặp đều khớp và chuỗi hợp lệ.

Vì sao đúng

Ngăn xếp phản ánh đúng thứ tự lồng nhau của ngoặc, ngoặc đóng luôn phải khớp với ngoặc mở gần nhất chưa đóng ở đỉnh.

Mã Python

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for i, c in enumerate(s):
        if c in "([{":
            stack.append((c, i))
        else:
            top, j = stack.pop()
            if top != pairs[c]:
                return False
    return not stack

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.