Editorial for meet: Địa điểm họp mặt

Hiểu bài toán

Bài toán yêu cầu lọc và in ra danh sách các địa điểm được đề xuất mà không chứa một ký tự c cụ thể. Đầu vào gồm số lượng địa điểm N, ký tự c không mong muốn, và N tên địa điểm. Đầu ra là danh sách các địa điểm không chứa ký tự c, mỗi địa điểm trên một dòng.

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

Cách Duyệt thủ công từng ký tự

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

int main() {
    int n;
    char c;
    scanf("%d %c", &n, &c);
    getchar();
    char s[101];
    for (int i = 0; i < n; i++) {
        fgets(s, 101, stdin);
        s[strcspn(s, "\n")] = '\0';
        int found = 0;
        for (int j = 0; s[j] != '\0'; j++) {
            if (s[j] == c) {
                found = 1;
                break;
            }
        }
        if (!found) printf("%s\n", s);
    }
    return 0;
}

• Time Complexity: O(N * L), với L là độ dài trung bình tên địa điểm (L ≤ 100)
• Space Complexity: O(1) (không kể bộ nhớ cho input)

Phương pháp này sử dụng vòng lặp lồng nhau: vòng lặp ngoài để duyệt qua từng địa điểm, vòng lặp trong để kiểm tra từng ký tự của địa điểm đó. Nếu không tìm thấy ký tự c, in ra địa điểm. Đây là cách tiếp cận trực quan nhất.

Cách Sử dụng hàm strchr

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

int main() {
    int n;
    char c;
    scanf("%d %c", &n, &c);
    char s[101];
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        if (strchr(s, c) == NULL) {
            printf("%s\n", s);
        }
    }
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(1)

Sử dụng hàm strchr từ thư viện string.h để kiểm tra sự tồn tại của ký tự c trong chuỗi. Hàm trả về con trỏ đến ký tự đầu tiên tìm thấy hoặc NULL nếu không có. Code ngắn gọn, dễ đọc và hiệu quả.

Cách Sử dụng hàm strstr (tương tự strchr)

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

int main() {
    int n;
    char c;
    scanf("%d %c", &n, &c);
    char s[101];
    char target[2];
    target[0] = c;
    target[1] = '\0';
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        if (strstr(s, target) == NULL) {
            printf("%s\n", s);
        }
    }
    return 0;
}

• Time Complexity: O(N * L)
• Space Complexity: O(1)

Tương tự strchr nhưng strstr dùng để tìm chuỗi con. Có thể dùng strstr(s, &c) nhưng không an toàn. Cách này minh họa cách chuyển ký tự thành chuỗi con để tìm kiếm.

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

Bài học kinh nghiệm

• Sử dụng hàm strchr là cách hiệu quả nhất để kiểm tra sự t tồn tại của một ký tự trong chuỗi C
• Cần chú ý xử lý ký tự newline khi dùng fgets để tránh sai lệch đầu vào

Lỗi thường gặp

• Quên xử lý ký tự newline sau khi dùng fgets có thể dẫn đến so sánh sai
• Sử dụng scanf("%s") cho mỗi địa điểm sẽ tự động bỏ qua khoảng trắng, nhưng đảm bảo tên địa điểm không chứa khoảng trắng theo đề bài
• Độ dài mảng char phải đủ để chứa tên địa điểm + ký tự kết thúc '\0'