20. Valid Parentheses

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/valid-parentheses/description/

Table of Contents

1. Cách tiếp cận vấn đề

Cho trước input string với các loại cặp dấu ngoặc '(', ')', '{', '}', '[' và ']', hãy xác định xem liệu input string đó có hợp lệ hay không:

1. Các dấu mở ngoặc phải được đóng lại với cùng một loại ngoặc.
2. Các dấu mở ngoặc phải được đóng lại theo đúng thứ tự.
3. Mỗi dấu đóng ngoặc phải có tương ứng với một dấu mở ngoặc cùng loại xuất hiện trước đó.

Từ những nguyên tắc trên, ta có thể đưa ra các ví dụ về input string có thể vi phạm:

1. Các dấu mở ngoặc bị đóng nhầm với loại ngoặc khác hoặc không được đóng bởi bất kỳ ngoặc nào: "{]", "(}", "[()", "(()"...
2. Các dấu mở ngoặc bị đóng lại theo sai thứ tự, nói cách khác số lượng các cặp đóng mở ngoặc là hợp lệ nhưng chỉ bị sai thứ tự: "([)]", "[{}(])"
3. Số lượng các dấu đóng ngoặc nhiều hơn dấu mở ngoặc và có từ một dấu đóng ngoặc không tìm được dấu đóng ngoặc phù hợp trước đó: "()]", "))", "}"
   

Nói tóm lại, ta cần đảm bảo:

1. Số lượng dấu mở ngoặc mỗi loại = Số lượng dấu đóng ngoặc mỗi loại
2. Các cặp ngoặc phải được đóng mở theo thứ tự xuất hiện của dấu mở ngoặc: Dấu mở ngoặc nào xuất hiện trước thì ta phải đóng dấu ngoặc đó sau cùng và ngược lại.

2. Solution & Phân Tích

Ta cần tìm ra một cấu trúc dữ liệu có thể đáp ứng được các yêu cầu đã nêu cùng với 1 giải thuật phù hợp. Dựa vào ý số 2 ở trên, nó khá giống với tính chất LIFO (Last In First Out) của Stack -> Ngoặc nào tới sau thì được đem ra xử lý đầu tiên và ngược lại, ví dụ: "([])" ngoặc "[" xuất hiện sau ngoặc "(" nên sẽ được đóng trước.

Chính vì vậy ta sẽ sử dụng thêm Stack để hỗ trợ lưu trữ và mỗi khi ta duyệt qua một dấu ngoặc, nếu:

• Đó là dấu mở ngoặc thuộc loại bất kỳ, ta sẽ push dấu đóng ngoặc tương ứng với nó vào stack. Ví dụ nếu "(" thì sẽ push ")".
• Đó là dấu đóng ngoặc x, ta sẽ kì vọng phần tử mà ta lấy được từ stack hiện tại chính là dấu đóng ngoặc x đó, nếu stack bị empty (trước đó chưa có dấu mở ngoặc nào) hoặc giá trị pop từ stack không phải là x (trước đó có dấu mở ngoặc nhưng thuộc loại khác x) thì ta có thể return false (String input không hợp lệ).

Sau cùng khi xử lý qua hết tất cả các ngoặc thì stack phải rỗng, nếu stack còn phần tử nào thì chứng tỏ có tồn tại những ngoặc chưa được đóng, trong trường hợp đó ta sẽ return false, ngược lại return true.

Time-Complexity: O(n)

Space-Complexity: O(n)

Với n là số lượng các dấu ngoặc trong chuỗi input.

3. Code