Mô tả
Tuần trước, đội vận hành của bạn trải qua một trận khủng hoảng thực sự: một tệp cấu hình hạ tầng bị lỗi cú pháp đã đẩy toàn bộ cụm dịch vụ xuống trạng thái nghỉ việc suốt hai tiếng đồng hồ. Sự cố này khiến mọi người nhớ lại báo cáo của cơ quan an ninh mạng Hoa Kỳ — trong một cuộc tấn công lớn, chính nhóm phản ứng sự cố của họ đã phải soạn tài liệu xử lý tay ngay giữa lúc đang chữa cháy, vì quy trình sẵn có không đủ độ phủ. Bài học rút ra rất rõ ràng: mọi cấu hình tự động đều phải được kiểm tra tính hợp lệ trước khi đi vào hệ thống production.
Hôm nay, bạn được giao viết một bước kiểm tra nhỏ nhưng then chốt trong pipeline xác thực manifest. Mỗi dòng khai báo cấu hình được biểu diễn dưới dạng một chuỗi chỉ chứa các dấu ngoặc: ngoặc tròn ( ), ngoặc vuông [ ] và ngoặc nhọn { }. Một chuỗi được xem là hợp lệ khi:
- Mỗi dấu ngoặc mở đều có đúng một dấu ngoặc đóng cùng loại tương ứng nằm phía sau nó.
- Các cặp ngoặc không được phép cắt nhau, ví dụ
[(])là không hợp lệ. - Cuối chuỗi không được tồn tại dấu ngoặc mở nào còn "trống": chưa gặp đóng.
Nhiệm vụ của bạn: cho một chuỗi biểu diễn cấu trúc khai báo, hãy trả về true nếu nó hợp lệ, ngược lại trả về false.
Đầu vào
- Một chuỗi
schỉ gồm các ký tự trong tập hợp{ '(', ')', '[', ']', '{', '}' }.
Đầu ra
- Trả về
truenếu chuỗi dấu ngoặc hợp lệ,falsenếu không hợp lệ.
Ràng buộc
- Độ dài chuỗi
nthỏa mãn0 <= n <= 10^4. - Chuỗi chỉ chứa đúng sáu loại ký tự đã liệt kê, không có ký tự nào khác.
Ví dụ
Ví dụ 1:
- Đầu vào:
"([]){}" - Đầu ra:
true
Giải thích: Duyệt từ trái qua phải — gặp ( ta đẩy vào ngăn xếp. Gặp [ tiếp tục đẩy. Gặp trùng khớp với trên đỉnh nên rút ra. Gặp trùng khớp với nên rút tiếp. Cuối cùng gặp đẩy vào rồi gặp rút ra. Kết thúc chuỗi, ngăn xếp trống nên chuỗi hợp lệ.