Hiểu bài toán

Bài toán yêu cầu chuẩn hóa các tên riêng trong danh sách. Tên riêng cần được viết hoa chữ cái đầu mỗi từ và viết thường các chữ cái còn lại. Danh sách input gồm T tên riêng, mỗi tên có thể chứa số và ký tự đặc biệt, không có khoảng trắng thừa. Ví dụ: 'lAp Trinh Khong Kho' được chuẩn hóa thành 'Lap Trinh Khong Kho'.

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

Cách Duyệt ký tự và xử lý điều kiện

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

int main(void) {
    int T;
    scanf("%d", &T);
    getchar(); 

    while (T--) {
        char *s = malloc(100);
        fgets(s, 100, stdin);

        int i;
        for (i = 0; i < strlen(s); i++) {
            if (i == 0 || s[i - 1] == ' ') {
                if (s[i] >= 'a' && s[i] <= 'z')
                    s[i] -= 32;
            } else {
                if (s[i] >= 'A' && s[i] <= 'Z')
                    s[i] += 32;
            }
        }

        printf("%s", s);
        free(s);
    }

    return 0;
}

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

Phương pháp này duyệt qua từng ký tự của chuỗi. Nếu ký tự là ký tự đầu tiên hoặc ký tự trước đó là dấu cách, nó kiểm tra xem ký tự hiện tại có phải là chữ cái thường không và chuyển thành in hoa (bằng cách trừ 32 trong bảng mã ASCII). Ngược lại, nếu không phải là ký tự đầu tiên hay sau dấu cách, nó kiểm tra xem ký tự có phải là in hoa không và chuyển thành in thường (bằng cách cộng 32). Cách này xử lý trực tiếp các quy tắc in hoa/in thường dựa trên vị trí của ký tự.

Cách Sử dụng biến cờ (Flag)

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
int main()
{
    int T;
    scanf("%d",&T);
    getchar();
    while(T>0)
    {
        char c[105];
        gets(c);
        if(c[0]>='a' && c[0]<='z') c[0]-=32;
        int check=0;
        for(int i=1;i<strlen(c);i++)
        {
            if(c[i]>='A' && c[i]<='Z' && check==0) c[i]+=32;
            if(c[i]>='A' && c[i]<='Z' && check==1) check=0;
            if(c[i]==' ') check=1;
            if(c[i]>='a' && c[i]<='z' && check==1)
            {
                c[i]-=32; check=0;
            }
        }
        printf("%s\n",c);
        T--;
    }
}

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

Phương pháp này cũng duyệt chuỗi nhưng sử dụng biến 'check' để đánh dấu việc có gặp dấu cách hay không. Ban đầu, ký tự đầu tiên được xử lý riêng. Trong vòng lặp từ ký tự thứ 2: Nếu gặp dấu cách, bật cờ 'check'. Nếu gặp ký tự in hoa và cờ đang bật (sau dấu cách), giữ nguyên và tắt cờ. Nếu gặp ký tự in hoa và cờ tắt, chuyển thành in thường. Nếu gặp ký tự thường và cờ bật, chuyển thành in hoa và tắt cờ. Logic này hơi phức tạp và dễ gây lỗi nếu xử lý các trường hợp đặc biệt không kỹ.

Cách Sử dụng thư viện chuẩn (ctype.h)

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

int main() {
    int t;
    scanf("%d", &t);
    getchar();   // bỏ \n sau số t

    while(t--) {
        char n[105];
        fgets(n, sizeof(n), stdin);
        n[strcspn(n, "\n")] = '\0';  // xoá \n

        int len = strlen(n);

        if (len > 0) n[0] = toupper(n[0]);

        for (int i = 1; i < len; i++) {
            if (n[i - 1] == ' ')
                n[i] = toupper(n[i]);
            else
                n[i] = tolower(n[i]);
        }

        printf("%s\n", n);
    }
    return 0;
}

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

Đây là cách tiếp cận chuẩn mực và dễ hiểu nhất. Nó sử dụng thư viện <ctype.h> với các hàm toupper và tolower. Chuỗi được duyệt từ đầu đến cuối. Ký tự đầu tiên luôn được chuyển thành in hoa. Với các ký tự tiếp theo, nếu ký tự trước đó là dấu cách thì ký tự hiện tại được chuyển thành in hoa, ngược lại thì chuyển thành in thường. Việc sử dụng hàm có sẵn giúp code ngắn gọn, dễ đọc và tránh các lỗi tính toán số học với bảng mã ASCII.

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

Bài học kinh nghiệm

• Cốt lõi bài toán là xác định vị trí của các từ (word boundaries),通常 là ký tự đầu tiên hoặc sau dấu cách.
• Mặc dù input có thể chứa số và ký tự đặc biệt, ta chỉ cần quan tâm đến việc chuyển đổi các ký tự chữ cái (A-Z, a-z). Các ký tự khác sẽ không thay đổi.
• Sử dụng thư viện chuẩn (như <ctype.h>) giúp code trở nên an toàn và dễ đọc hơn so với việc tự tính toán offset trong bảng mã ASCII.

Lỗi thường gặp

• Bỏ qua ký tự newline (\n) từ input trước khi xử lý, đặc biệt khi trộn lẫn scanf và fgets/gets.
• Xử lý sai chuỗi rỗng hoặc chuỗi chỉ chứa dấu cách.
• Lỗi logic khi kiểm tra điều kiện 'ký tự trước đó là dấu cách': cần đảm bảo không truy cập ngoài biên mảng (ví dụ: ở index -1).