Kiểm tra ngoặc cân bằng O(1) không gian, O(N²) thời gian trong C++

Khái niệm

Cho chuỗi chứa các ký tự '(', ')', '{', '}', '[', ']'. Kiểm tra xem ngoặc có cân bằng hay không. Cân bằng nghĩa là: ngoặc mở phải đóng bằng cùng loại, và đúng thứ tự lồng nhau.

Ví dụ: "(()){}" → Yes; "))(([][" → No.

Phương pháp (O(1) space)

• Dùng hai chỉ số a, b theo dõi vị trí ngoặc so khớp.
• Biến count: tăng khi gặp ngoặc mở, giảm khi gặp ngoặc đóng.
• Khi gặp ngoặc đóng: so sánh với ngoặc mở tại vị trí b. Nếu khớp → thay cả hai bằng '#', dịch b về trước qua các '#', tăng a. Nếu không khớp → false.
• Cuối cùng count phải = 0.

Ví dụ (C++)

#include <iostream>
using namespace std;

bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
    count1--;
    if (j1 > -1 && s1[j1] == tocom1) {
        s1[i1] = '#'; s1[j1] = '#';
        while (j1 >= 0 && s1[j1] == '#') j1--;
        i1++; return 1;
    }
    return 0;
}

bool isValid(string s1){
    if (s1.empty()) return true;
    int i1 = 0, count1 = 0, j1 = -1;
    while (i1 < s1.length()) {
        switch (s1[i1]) {
            case '}': if (!helperFunc(count1, s1, i1, j1, '{')) return false; break;
            case ')': if (!helperFunc(count1, s1, i1, j1, '(')) return false; break;
            case ']': if (!helperFunc(count1, s1, i1, j1, '[')) return false; break;
            default: j1 = i1; i1++; count1++;
        }
    }
    return count1 == 0;
}

int main(){
    string str1 = "[[]][]()";
    if (isValid(str1)) cout << "Yes"; else cout << "No";
    return 0;
}

Đầu ra

Yes