Hiểu bài toán

Bài toán yêu cầu kiểm tra một xâu gồm các ký tự ngoặc đơn '(', ngoặc vuông '[', ngoặc nhọn '{' và các ký tự đóng tương ứng ')', ']', '}' có phải là một dãy ngoặc đúng hay không. Một dãy ngoặc đúng phải thỏa mãn các điều kiện: (1) Mỗi cặp ngoặc mở phải được đóng bởi cùng loại ngoặc. (2) Các cặp ngoặc phải được đóng theo đúng thứ tự (ngoặc mở sau cùng phải được đóng trước tiên). (3) Xâu phải kết thúc khi tất cả các cặp ngoặc đều được đóng.

Các cách tiếp cận

Cách Sử dụng String (Simulated Stack)

#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
    cin >> s;
    string st;
    bool ok = true;
    for (char c : s){
        if (c == '(' || c == '[' || c == '{'){
            st.push_back(c);
        }
        else{
            if (st.empty()){
                ok = false;
                break;
            }
            char top = st.back(); 
            st.pop_back();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')){
                ok = false;
                break;
            }
        }
    }
    if (!st.empty()) ok = false;
    cout << (ok ? "Yes" : "No");
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Phương pháp này sử dụng một xâu ký tự string như một ngăn xếp (stack). Khi gặp ngoặc mở, ta nối ký tự đó vào cuối xâu. Khi gặp ngoặc đóng, ta kiểm tra ký tự cuối cùng của xâu (tương ứng với ngoặc mở chưa đóng gần nhất). Nếu khớp, ta xóa ký tự đó khỏi xâu. Nếu không khớp hoặc xâu rỗng khi gặp ngoặc đóng, xâu sai. Sau khi duyệt hết, nếu xâu rỗng thì đúng, ngược lại sai. Cách này đơn giản để viết nhưng có thể chậm hơn stack do việc cấp phát bộ nhớ động liên tục, mặc dù vẫn được chấp nhận với giới hạn 10^5.

Cách Sử dụng Stack

#include <bits/stdc++.h>
using namespace std;

int check(string s){
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return 0;
            char top = st.top(); st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return 0;
            }
        }
    }
    return st.empty();
}

int main(){
    string s;
    cin >> s;
    if (check(s)) cout << "Yes";
    else cout << "No";
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận chuẩn và hiệu quả nhất. Ta sử dụng thư viện chuẩn std::stack. Khi duyệt xâu, nếu là ngoặc mở ((, [, {), ta push vào stack. Nếu là ngoặc đóng, ta so sánh với top của stack. Nếu khớp, ta pop stack. Nếu stack rỗng khi gặp ngoặc đóng hoặc loại không khớp, trả về false. Sau cùng, kiểm tra xem stack có rỗng không. Độ phức tạp thời gian và không gian đều là O(n).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Ngăn xếp (Stack) là cấu trúc dữ liệu lý tưởng cho bài toán này vì tính chất LIFO (Last In First Out) - ngoặc mở gần nhất phải được đóng trước tiên.
• Cần kiểm tra hai điều kiện sai khi gặp ngoặc đóng: (1) Ngăn xếp rỗng (có ngoặc đóng mà không có ngoặc mở tương ứng), (2) Loại ngoặc đóng không trùng với ngoặc mở ở đỉnh ngăn xếp.

Lỗi thường gặp

• Quên kiểm tra xem stack có rỗng không trước khi truy cập top() hoặc pop() có thể gây lỗi truy cập bộ nhớ (segmentation fault).
• Quên kiểm tra xem stack còn rỗng sau khi đã duyệt hết chuỗi. Nếu stack không rỗng, nghĩa là còn các ngoặc mở chưa được đóng, dẫn đến kết quả sai.