20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

class Solution {

public:

    bool isValid(string s) {

        if (s.length() % 2 != 0) return false;

        // Vì ngoặc luôn đi theo cặp, độ dài lẻ chắc chắn là sai.

        unordered_map <char,char> mp ={

            {')', '('},

            {'}','{'},

            {']','['}

        };

        stack<char> st;

        for (char c: s){

            if(c == '(' || c== '{' || c== '['){

                st.push(c);

            }else{

                if(st.empty() || st.top() != mp[c]){

                    return false;

                }

                st.pop();

            }

        }

        return st.empty();

    }

};

Chạy từng bước (dry run) với input s = "([)]"

Giả sử bảng tra cứu mp của chúng ta là:

• ) => (

• ] => [

• } => {

Quá trình Dry Run

Khởi tạo: stack<char> st (rỗng).

Phân tích chi tiết tại Bước 3:

Khi gặp ký tự ), chương trình sẽ thực hiện các lệnh sau:

1. Kiểm tra st.empty(): Stack hiện có 2 phần tử nên không trống.

2. Lấy phần tử trên cùng: st.top() trả về '['.

3. Tra cứu mã khớp: mp[')'] trả về '('.

4. So sánh: st.top() != mp[')'] tương đương với '[' != '('.

Vì hai ký tự này không khớp nhau, điều kiện if được thỏa mãn và hàm ngay lập tức return false.

Tại sao nó lại hoạt động như vậy?

Trong cấu trúc ngoặc hợp lệ, dấu ngoặc đóng phải khớp với dấu ngoặc mở gần nó nhất chưa được đóng.

• Ở bước 3, dấu ngoặc mở gần nhất là [ (nằm ở đỉnh stack).

• Nhưng dấu ngoặc đóng xuất hiện lại là ).

• Việc "đóng nhảy cóc" này vi phạm quy tắc: Open brackets must be closed in the correct order.

Kết luận: Chuỗi "([)]" là không hợp lệ vì dấu ( bị chặn bởi dấu [ chưa đóng, nên nó không thể "gặp" dấu ) của mình được.