Editorial for demso: Đếm số trong chuỗi

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các con số xuất hiện trong một xâu ký tự. Một 'số' được định nghĩa là một dãy các ký tự số liên tiếp (từ '0' đến '9'). Các số có thể nằm xen kẽ với các ký tự chữ cái hoặc ký tự đặc biệt. Ví dụ, trong xâu 'A0123b345', có hai số là '0123' và '345'.

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

Cách Duyệt chuỗi và kiểm tra điều kiện

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

char s[1000001];

int main() {
    scanf("%s", s);
    int count = 0;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        // Nếu ký tự hiện tại là số
        if (s[i] >= '0' && s[i] <= '9') {
            // Kiểm tra xem đây có phải là bắt đầu của một số mới không:
            // 1. Nó là ký tự đầu tiên của xâu (i == 0)
            // 2. Ký tự ngay trước nó KHÔNG phải là số
            if (i == 0 || (s[i-1] < '0' || s[i-1] > '9')) {
                count++;
            }
        }
    }

    printf("%d", count);
    return 0;
}

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

Thuật toán này duyệt qua từng ký tự của xâu. Nếu gặp một ký tự số, nó kiểm tra xem ký tự này có phải là ký tự số đầu tiên trong một dãy số liên tiếp hay không. Điều kiện để một ký tự số là đầu dãy là: nó phải là ký tự đầu tiên của xâu, hoặc ký tự ngay trước nó không phải là ký tự số (nó là chữ cái hoặc ký tự đặc biệt). Mỗi khi điều kiện này thỏa mãn, biến đếm count được tăng lên 1. Cuối cùng, in ra giá trị của count.

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

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

char s[1000001];

int main() {
    scanf("%s", s);
    int count = 0;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        if (isdigit(s[i])) {
            // Nếu ký tự hiện tại là số VÀ
            // (nó là ký tự đầu tiên HOẶC ký tự trước đó không phải là số)
            if (i == 0 || !isdigit(s[i-1])) {
                count++;
            }
        }
    }

    printf("%d", count);
    return 0;
}

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

Cách tiếp cận này tương tự như cách đầu tiên, nhưng sử dụng hàm isdigit() từ thư viện <ctype.h> để kiểm tra xem một ký tự có phải là số hay không. Hàm này giúp mã nguồn dễ đọc và chuẩn hóa hơn so với việc tự so sánh ký tự. Logic đếm số lượng các dãy số vẫn giữ nguyên: đếm mỗi khi gặp một ký tự số mà không có ký tự số nào ngay trước nó.

Cách Xử lý ký tự từng cái (One-by-one)

#include <stdio.h>
#include <ctype.h>

int main() {
    char c;
    int count = 0;
    int in_number = 0; // Biến c cờ, 1 nếu đang ở trong một dãy số, 0 nếu không

    while (scanf("%c", &c) == 1) {
        if (c == '\n') break; // Dừng lại khi gặp ký tự newline

        if (isdigit(c)) {
            // Nếu gặp số và đang không ở trong dãy số nào trước đó
            if (in_number == 0) {
                count++;
                in_number = 1; // Đánh dấu là đang ở trong dãy số
            }
        } else {
            // Nếu gặp ký tự không phải số, reset cờ
            in_number = 0;
        }
    }

    printf("%d", count);
    return 0;
}

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

Phương pháp này đọc dữ liệu đầu vào từng ký tự một thay vì đọc cả xâu. Nó sử dụng một biến c cờ (ví dụ là in_number) để theo dõi trạng thái hiện tại của bộ duyệt. Nếu in_number là 0 và gặp một ký tự số, ta biết rằng đây là bắt đầu của một số mới, vì vậy tăng biến đếm và đặt in_number thành 1. Nếu in_number là 1 và vẫn gặp số, ta bỏ qua. Nếu gặp bất kỳ ký tự nào không phải số, ta đặt in_number trở về 0. Ưu điểm của cách này là nó chỉ cần bộ nhớ cố định (O(1)), không cần lưu trữ toàn bộ xâu đầu vào.

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

Bài học kinh nghiệm

• Một dãy số liên tiếp được coi là một đối tượng duy nhất. Vấn đề cốt lõi là đếm số lượng các dãy số, không phải tổng số ký tự số.
• Điều kiện để bắt đầu đếm một dãy số mới là khi ta gặp một ký tự số và ký tự ngay trước nó (nếu có) không phải là ký tự số.
• Có thể giải quyết bài toán này mà không cần lưu trữ toàn bộ xâu đầu vào bằng cách xử lý đầu vào theo luồng (stream processing).

Lỗi thường gặp

• Đếm nhầm: Đếm mỗi ký tự số riêng lẻ thay vì đếm các dãy số. Ví dụ, với '123', sẽ đếm sai thành 3 thay vì 1.
• Bỏ qua trường hợp số ở đầu xâu: Cần kiểm tra điều kiện i == 0 để xử lý đúng trường hợp xâu bắt đầu bằng số.
• Lỗi truy cập bộ nhớ: Truy cập s[i-1] khi i == 0 sẽ gây lỗi bộ nhớ (vùng nhớ âm), cần kiểm tra i == 0 trước.