Trong lập trình, bài toán "Valid Parentheses" (Kiểm tra dấu ngoặc hợp lệ) là một bài toán kinh điển, thường được sử dụng để đánh giá khả năng tư duy logic và kỹ năng sử dụng cấu trúc dữ liệu của lập trình viên. Bài toán yêu cầu kiểm tra xem một chuỗi ký tự chứa các dấu ngoặc có hợp lệ hay không, nghĩa là các dấu ngoặc mở và đóng phải được ghép đôi đúng cách.
Định nghĩa bài toán
Cho một chuỗi chỉ chứa các ký tự dấu ngoặc như (, ), {, }, [, ], hãy xác định xem chuỗi đó có hợp lệ hay không. Một chuỗi được coi là hợp lệ nếu:
Mỗi dấu ngoặc mở phải có một dấu ngoặc đóng tương ứng cùng loại. Các dấu ngoặc phải được đóng theo đúng thứ tự. Không có dấu ngoặc đóng nào xuất hiện trước dấu ngoặc mở tương ứng.
Ví dụ:
"()" → Hợp lệ
"()[]{}" → Hợp lệ
"(]" → Không hợp lệ
"([)]" → Không hợp lệ
"{[]}" → Hợp lệ
Cách tiếp cận giải quyết
Để giải bài toán này, cấu trúc dữ liệu stack (ngăn xếp) thường được sử dụng vì đặc tính "vào sau, ra trước" (LIFO - Last In, First Out) của nó rất phù hợp để kiểm tra thứ tự ghép đôi các dấu ngoặc.
Thuật toán
- Khởi tạo một stack rỗng để lưu trữ các dấu ngoặc mở.
- Duyệt qua từng ký tự trong chuỗi: Nếu ký tự là dấu ngoặc mở ((, {, [), đẩy nó vào stack.
Nếu ký tự là dấu ngoặc đóng (), }, ]):
Kiểm tra xem stack có rỗng hay không. Nếu rỗng, chuỗi không hợp lệ (vì không có dấu ngoặc mở tương ứng).
Lấy dấu ngoặc mở trên cùng của stack và kiểm tra xem nó có khớp với dấu ngoặc đóng hiện tại hay không. Nếu không khớp, chuỗi không hợp lệ.
- Sau khi duyệt hết chuỗi, kiểm tra stack:
Nếu stack rỗng, chuỗi hợp lệ (tất cả dấu ngoặc đã được ghép đôi).
Nếu stack không rỗng, chuỗi không hợp lệ (còn dấu ngoặc mở chưa được đóng).
Triển khai bằng Python
def isValid(s: str) -> bool: stack = [] brackets = {')': '(', '}': '{', ']': '['} for char in s: if char in brackets.values(): stack.append(char) elif char in brackets: if not stack or stack.pop() != brackets[char]: return False return len(stack) == 0
Giải thích code:
Biến brackets là một từ điển lưu trữ ánh xạ giữa dấu ngoặc đóng và dấu ngoặc mở tương ứng.
Với mỗi ký tự trong chuỗi:
Nếu là dấu ngoặc mở, thêm vào stack.
Nếu là dấu ngoặc đóng, kiểm tra stack và dấu ngoặc mở trên cùng.
Cuối cùng, kiểm tra xem stack có rỗng hay không để xác định kết quả.
Phân tích độ phức tạp
Độ phức tạp thời gian: O(n), trong đó n là độ dài chuỗi. Mỗi ký tự được duyệt đúng một lần, và các thao tác stack (push, pop) có độ phức tạp O(1).
Độ phức tạp không gian: O(n) trong trường hợp xấu nhất, khi tất cả ký tự là dấu ngoặc mở và được đẩy vào stack.
Ứng dụng thực tế
Kiểm tra dấu ngoặc hợp lệ không chỉ là bài toán học thuật mà còn có ứng dụng thực tế:
Biên dịch mã nguồn: Trong các trình biên dịch, kiểm tra dấu ngoặc hợp lệ giúp phát hiện lỗi cú pháp trong mã nguồn (ví dụ: { không có } tương ứng).
Xử lý biểu thức toán học: Đảm bảo các biểu thức toán học hoặc logic có cấu trúc hợp lệ.
Trình soạn thảo văn bản: Các IDE sử dụng thuật toán này để tự động kiểm tra và báo lỗi khi người dùng nhập dấu ngoặc không khớp.
Kết luận Bài toán Valid Parentheses là một ví dụ tuyệt vời để rèn luyện kỹ năng sử dụng stack và tư duy logic. Với cách tiếp cận đơn giản nhưng hiệu quả, thuật toán này không chỉ giúp giải quyết bài toán mà còn có thể áp dụng vào nhiều tình huống thực tế trong lập trình. Việc nắm vững bài toán này sẽ là nền tảng để giải quyết các bài toán phức tạp hơn liên quan đến cấu trúc dữ liệu và xử lý chuỗi.