Editorial for Cánh cửa khép hờ

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Thứ tự lồng nhau

Khi gặp dấu ngoặc mở, chưa thể biết nó sẽ đóng ở đâu nên cần ghi nhớ nó. Các dấu mở được đóng theo thứ tự ngược lại với lúc mở.

Gợi ý 2 - Dùng ngăn xếp

Đẩy mỗi dấu mở vào stack. Khi gặp dấu đóng, nó phải khớp với dấu mở trên đỉnh stack. Nếu stack rỗng hoặc hai dấu khác loại, chuỗi sai. Cuối cùng stack cũng phải rỗng.

Lời giải đầy đủ

Ý tưởng

Duyệt chuỗi từ trái sang phải. Stack lưu các dấu mở chưa được ghép. Với dấu đóng, kiểm tra đỉnh stack rồi lấy dấu mở đó ra. Điều này bảo đảm mỗi dấu đóng ghép với dấu mở gần nhất còn chưa khép, đúng với quy tắc lồng nhau.

Nếu gặp dấu đóng khi stack rỗng, gặp sai loại ngoặc, hoặc còn dấu mở sau khi duyệt hết chuỗi thì in NO; các trường hợp còn lại in YES.

Độ phức tạp

Mỗi ký tự được xử lý đúng một lần. Thời gian O(|S|), bộ nhớ O(|S|).

Code C++17

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

bool matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    stack<char> st;
    bool correct = true;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty() || !matches(st.top(), c)) {
                correct = false;
                break;
            }
            st.pop();
        }
    }

    if (!st.empty()) correct = false;
    cout << (correct ? "YES" : "NO") << endl;
    return 0;
}