- vừa được xem lúc

Valid Parentheses - Kiểm tra dấu ngoặc hợp lệ

0 0 6

Người đăng: Nguyễn Ánh Dung

Theo Viblo Asia

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

  1. Khởi tạo một stack rỗng để lưu trữ các dấu ngoặc mở.
  2. 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ệ.

  1. 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.

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán quay lui (Backtracking)

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

0 0 60

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 184

- vừa được xem lúc

Sử dụng vector trong lập trình C++ - giải bài toán lập trình muôn thủa

Chào buổi tối mọi người, hôm nay lang thang trên mạng bắt gặp bài toán quen thuộc một thời của quãng đường sinh viên IT. Đấy chính là câu số 1 trong đề thi dưới đây:.

0 0 69

- vừa được xem lúc

MÔ PHỎNG THUẬT TOÁN VƯƠNG HẠO TRONG PROLOG

. 1. Các luật suy diễn trong thuật toán Vương Hạo. Luật 1: Chuyển vế các giả thuyết và kết luận ở dạng phủ định. Ví dụ: p v q, !(r ^ s), !q, p v r -> s, !p <=> p v q, p v r, p -> s, r ^ s, q.

0 0 102

- vừa được xem lúc

A* Search Algorithm

What is A* Search Algorithm. How it works. . Explanation.

0 0 64

- vừa được xem lúc

Python: Jump Search

Search là một từ khóa khá là quen thuộc đối với chúng ta. Hiểu theo đúng nghĩa đen của nó chính là "Tìm kiếm".

0 0 61