Editorial for lkngoac: Liệt kê cặp dấu ngoặc

Hiểu bài toán

Cho một dãy ngoặc đúng với n cặp ngoặc, được đánh số thứ tự từ 1 đến 2n. Nhiệm vụ là liệt kê n cặp chỉ số (u, v) tương ứng giữa dấu ngoặc mở '(' và dấu ngoặc đóng ')'. Yêu cầu thứ tự in ra phải tăng dần theo chỉ số của dấu ngoặc đóng (v). Ví dụ: với input '()(())', ta có các cặp lần lượt là (1,2) và (3,6).

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

Cách Dùng mảng động (Stack ẩn)

#include <stdio.h>
#include <string.h>

char s[200005];
int b[200005]; // Mảng lưu chỉ số dấu ngoặc mở
int k = 0; // Biến đỉnh stack

int main(){
    scanf("%s", s);
    int n = strlen(s);
    for(int i = 0; i < n; i++){
        if(s[i] == '('){
            b[k++] = i + 1; // Lưu chỉ số (bắt đầu từ 1)
        } else {
            // In ra cặp ngoặc (mở, đóng)
            printf("%d %d\n", b[k-1], i + 1);
            k--; // Loại bỏ dấu ngoặc mở tương ứng
        }
    }
    return 0;
}

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

Đây là cách tiếp cận trực quan và hiệu quả nhất. Ta duyệt qua từng ký tự của dãy ngoặc. Khi gặp dấu ngoặc mở '(', ta lưu chỉ số của nó vào một mảng (tạm gọi là stack). Khi gặp dấu ngoặc đóng ')', ta biết rằng nó phải khớp với dấu ngoặc mở mới nhất chưa được khớp (đầu tiên vào cuối ra - LIFO). Do đó, ta lấy chỉ số ở đầu stack in ra cùng với chỉ số hiện tại, rồi giảm kích thước stack đi 1. Vì input là dãy ngoặc đúng, ta không cần kiểm tra lỗi. Phương pháp này đảm bảo thứ tự in ra tăng dần theo chỉ số đóng ngoặc vì ta duyệt tuần tự từ trái sang phải.

Cách Dùng Linked List (Stack)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    int index;
    struct node *link;
} node;

node* push(node *head, int id) {
    node *new_node = (node*)malloc(sizeof(node));
    new_node->index = id;
    new_node->link = head;
    return new_node;
}

node* pop(node *head) {
    node *temp = head;
    head = head->link;
    free(temp);
    return head;
}

int main() {
    char s[200005];
    scanf("%s", s);
    node *head = NULL;
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            head = push(head, i + 1);
        } else {
            printf("%d %d\n", head->index, i + 1);
            head = pop(head);
        }
    }
    return 0;
}

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

Cách này sử dụng cấu trúc dữ liệu Linked List để mô phỏng Stack. Mỗi khi gặp '(', ta tạo một node mới lưu chỉ số và chèn vào đầu danh sách. Khi gặp ')', ta in ra chỉ số từ node đầu danh sách và giải phóng bộ nhớ node đó. Dù khác biệt về cấu trúc, logic vẫn tương tự như cách dùng mảng: tìm dấu ngoặc mở chưa khớp gần nhất. Tuy nhiên, cách này thường chậm hơn và tốn bộ nhớ hơn do chi phí cấp phát phát sinh cho từng node, và truy cập bộ nhớ không liên tục (cache miss).

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

Bài học kinh nghiệm

• Tính chất LIFO (Last In First Out) của Stack là chìa khóa để giải quyết bài toán ghép cặp ngoặc.
• Vì dãy input luôn đúng, ta không cần kiểm tra tính hợp lệ mà chỉ cần ghép cặp.
• Thứ tự in ra yêu cầu tăng dần theo dấu ngoặc đóng正好 (đúng) bằng thứ tự duyệt từ trái sang phải khi gặp dấu ngoặc đóng.

Lỗi thường gặp

• Lỗi chỉ số: Nhầm lẫn giữa chỉ số trong code (bắt đầu từ 0) và chỉ số yêu cầu đầu ra (bắt đầu từ 1).
• Quên cập nhật biến đếm/đỉnh stack: Khi pop phần tử, phải giảm biến đếm (k--) hoặc cập nhật con trỏ head.
• Sử dụng quá nhiều bộ nhớ: Khai báo mảng stack quá lớn hoặc dùng Linked List gây tốn RAM không cần thiết so với mảng tĩnh.