Hiểu bài toán

Bài toán yêu cầu đếm số từ trong một đoạn văn bản cho trước. Đoạn văn bản chỉ bao gồm các chữ cái (A-Z, a-z) và dấu cách (' '). Một từ được định nghĩa là một chuỗi các chữ cái liên tiếp không chứa dấu cách. Các từ được phân tách bởi một hoặc nhiều dấu cách. Ví dụ, input "Thank you" có 2 từ. Vấn đề cần xử lý là nhận diện ranh giới giữa các từ, đặc biệt lưu ý các trường hợp nhiều dấu cách liên tiếp hoặc dấu cách ở đầu/cuối chuỗi.

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

Cách Sử dụng hàm strtok (Split String)

#include <stdio.h>
#include <string.h>
int main()
{
    char a[100001];
    fgets(a, sizeof(a), stdin);
    int n=strlen(a);
    if(n>0&&a[n-1]=='\n'){
    a[n- 1] = '\0';}
    char *token = strtok(a, " ");
    int cnt = 0;
    while (token != NULL)
    {
        ++cnt;
        token = strtok(NULL, " ");
    }
    printf("%d", cnt);
}

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

Cách tiếp cận này sử dụng thư viện chuẩn của C là strtok. Đầu tiên, input được đọc vào bằng fgets và loại bỏ ký tự newline ở cuối. Hàm strtok cắt xâu thành các token dựa trên dấu cách là delimiter. Trong vòng lặp while, mỗi khi strtoken trả về một token hợp lệ (khác NULL), ta tăng biến đếm cnt. Vì strtok mặc định coi nhiều dấu cách liên tiếp là một dấu cách phân tách, nó giải quyết đúng yêu cầu của bài toán.

Cách Duyệt tuần tự và đánh dấu trạng thái (State Tracking)

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

char s[101010];

void solve(){
    fgets(s, sizeof s, stdin);
    s[strcspn(s, "\n")] = '\0';
    int cnt = 0, last = 0;
    int nsize = strlen(s);

    for(int i = 0; i < nsize; i++){
        if(s[i] >= 'a' && s[i] <= 'z'){
            if(last == 0){
                last = 1;
                cnt++;
            }
        }
        else if(s[i] >= 'A' && s[i] <= 'Z'){
            if(last == 0){
                last = 1;
                cnt++;
            }
        }
        else {
            last = 0;
        }
    }
    printf("%d", cnt);
}

int main(){
    solve();
    return 0;
}

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

Phương pháp này duyệt qua từng ký tự của xâu. Ta sử dụng một biến last để ghi nhớ trạng thái của ký tự ngay trước đó. Nếu last == 0 (tức là ký tự trước đó là dấu cách hoặc chưa có ký tự nào) và ký tự hiện tại là chữ cái, ta hiểu đây là bắt đầu của một từ mới, do đó tăng biến đếm cnt và đặt last = 1. Nếu gặp dấu cách, ta đặt lại last = 0. Cách này kiểm soát hoàn toàn logic đếm và không phụ thuộc vào thư viện.

Cách Duyệt tuần tự kiểm tra ranh giới (Space Detection)

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

int main() {
    char s[100002];
    fgets(s, sizeof(s), stdin);
    int dem = 0, sp = 0;
    int l = strlen(s);

    if (s[l - 1] == '\n') {
        s[l - 1] = '\0';
        l--;
    }

    for(int i = 0; i < l; i++){
        if(!isspace(s[i])){
            if(sp == 0){
                dem++;
                sp = 1;
            }
        }
        else{
            sp = 0;
        }
    }

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

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

Giống như cách trên, phương pháp này cũng duyệt tuần tự. Tuy nhiên, nó sử dụng biến sp (space) để đánh dấu xem liệu ta có đang ở trong một chuỗi dấu cách hay không. Nếu gặp ký tự không phải dấu cách (!isspace) và sp == 0 (tức là vừa qua một dấu cách hoặc là đầu chuỗi), ta đếm từ và đặt sp = 1. Nếu gặp dấu cách, ta đặt sp = 0. Logic này đảm bảo rằng chỉ khi chuyển từ dấu cách sang chữ cái mới đếm.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng cách chia xâu (splitting) hoặc duyệt tuần tự (iteration).
• Cần xử lý ký tự newline cuối input khi dùng fgets.
• Logic đếm phải bỏ qua các dấu cách thừa ở đầu, cuối và giữa các từ.

Lỗi thường gặp

• Quên loại bỏ ký tự newline '\n' ở cuối input khi dùng fgets, dẫn đến lỗi logic nếu xử lý ký tự cuối.
• Sử dụng scanf để đọc input vì scanf sẽ dừng lại ở dấu cách đầu tiên, không đọc được cả câu.
• Lỗi logic khi duyệt tuần tự: đếm nhầm nếu không kiểm soát trạng thái (ví dụ: đếm 2 lần cho một từ nếu dùng điều kiện không chặt chẽ).