Editorial for name: Chuẩn hóa danh từ riêng

Hiểu bài toán

Cho một danh sách gồm n tên riêng, mỗi tên có thể có nhiều từ, các từ ngăn cách nhau bởi một hoặc nhiều khoảng trắng, và có thể có khoảng trắng ở đầu/cuối. Nhiệm vụ là chuẩn hóa các tên này sao cho:

1. Giữa các từ chỉ còn đúng một khoảng trắng, không có khoảng trắng thừa ở đầu hoặc cuối.
2. Chữ cái đầu tiên của mỗi từ viết hoa, các chữ cái còn lại viết thường. Ví dụ: " vIeT nAm " cần được chuyển thành "Viet Nam".

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

Cách Xử lý ký tự theo logic cờ (Flag-based)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long t;
    cin >> t;
    string n;
    cin.ignore();
    for(long long i=0;i<t;i++){
        getline(cin,n);
        string a="";
        long long dem=0;
        for(auto &i:n){
            if(isalpha(i)){
                if(dem==0) i=toupper(i);
                else i=tolower(i);
                dem=1;
            }
            else dem=0;
        }
        cout << n << endl;
    }
}

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

Phương pháp này sử dụng biến đếm (dem) như một cờ để xác định vị trí của các ký tự.

• Khi duyệt qua từng ký tự trong chuỗi:
  • Nếu là ký tự chữ (isalpha):
    • Nếu dem == 0 (tức là ký tự này là ký tự đầu tiên của một từ): Chuyển nó thành chữ hoa và đặt dem = 1.
    • Nếu dem == 1 (ký tự nằm trong từ): Chuyển nó thành chữ thường.
  • Nếu là ký tự trắng: Đặt dem = 0 để báo hiệu ký tự tiếp theo (nếu là chữ) sẽ là đầu từ.
• Nhược điểm: Phương pháp này chỉ sửa đổi casing và logic đếm từ, nhưng không xử lý vấn đề khoảng trắng thừa (dấu cách ở đầu/cuối hoặc nhiều dấu cách liên tiếp). Ví dụ, chuỗi " A b " vẫn giữ nguyên cấu trúc khoảng trắng sai của nó. Tuy nhiên, nó có thể passes các test case đơn giản vì chỉ tập trung vào requirement về hoa/thường.

Cách Duyệt và Xây dựng Chuỗi mới (String Building)

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long t; cin >> t;
    cin.ignore();
    while(t--){
        bool ok = false;
        string s, f = "";
        getline(cin, s);
        for(long long i = 0; i < s.size(); i++){
            if(s[i] == ' '){
                ok = true;
                f += ' ';
            }
            else if(s[i] != ' ' && ok){
                f += toupper(s[i]);
                ok = false;
            }
            else f += tolower(s[i]);
        }
        if(islower(f[0])) f[0] = toupper(f[0]);
        cout << f << endl;
    }
}

• Time Complexity: O(T * L)
• Space Complexity: O(L)

Phương pháp này tạo ra một chuỗi mới f để chứa kết quả.

• Biến ok dùng để đánh dấu rằng vừa gặp một khoảng trắng.
• Duyệt từng ký tự s[i]:
  • Nếu s[i] là khoảng trắng: Thêm một khoảng trắng vào f và bật cờ ok.
  • Nếu s[i] là chữ:
    • Nếu cờ ok đang bật (tức đây là ký tự đầu tiên sau khoảng trắng): Viết hoa và tắt cờ.
    • Ngược lại: Viết thường.
• Sau vòng lặp, kiểm tra thủ công ký tự đầu tiên của f nếu nó chưa được viết hoa (trường hợp từ đầu tiên là từ đầu chuỗi).
• Phương pháp này có thể loại bỏ khoảng trắng thừa nếu logic kiểm soát việc thêm khoảng trắng vào f là chính xác, nhưng đoạn code trên vẫn có thể thêm nhiều khoảng trắng nếu chuỗi đầu vào có nhiều khoảng trắng liên tiếp (vì mỗi lần gặp khoảng trắng đều f += ' ').

Cách Xử lý Chuỗi theo Dòng (Stream Processing)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    cin.ignore(1);
    for(int x = 0; x < n; x++){
        string s;
        getline(cin, s);
        s[0] = toupper(s[0]);
        for(int i = 0; i < s.size() - 1; i++){
            if(s[i] == ' ' && s[i+1] != ' ') s[i+1] = toupper(s[i+1]);
            else s[i+1] = tolower(s[i+1]);
        }
        cout << s << endl;
    }
}

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

Đây là cách tiếp cận trực tiếp và tối ưu nhất trong các solution được cung cấp.

• Logic:
  1. Đọc chuỗi vào s.
  2. Luôn viết hoa ký tự đầu tiên s[0].
  3. Duyệt từ i = 0 đến hết chuỗi:
     • Nếu s[i] là khoảng trắng và s[i+1] là chữ: s[i+1] là đầu từ mới -> Viết hoa.
     • Ngược lại (ký tự thường hoặc khoảng trắng liên tiếp): s[i+1] là phần thân từ -> Viết thường.
• Ưu điểm:
  • Xử lý đúng requirement về hoa/thường cho mọi ký tự.
  • Dù không loại bỏ khoảng trắng thừa theo nghĩa vật lý (xóa ký tự), nhưng việc chuẩn hóa casing theo logic này (chỉ viết hoa sau khoảng trắng nếu có chữ, và viết thường các ký tự còn lại) đảm bảo dữ liệu văn bản được xử lý đúng nếu hệ thống coi trọng cấu trúc dòng.
• Code này sửa đổi trực tiếp chuỗi s hiện có (in-place), tiết kiệm bộ nhớ.

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

Bài học kinh nghiệm

• Bài toán có hai phần: xử lý khoảng trắng và xử lý hoa/thường. Để xử lý triệt để cả hai, cần phân tách các từ (tokenize) và nối lại.
• Logic 'ký tự nào đi sau khoảng trắng là chữ hoa' là chìa khóa, nhưng cần phân biệt giữa khoảng trắng là separator và khoảng trắng là noise.
• Dùng cin.ignore() sau khi đọc n là bắt buộc để xóa ký tự newline còn lại trong bộ đệm trước khi dùng getline.

Lỗi thường gặp

• Quên cin.ignore(): Nếu không xóa bộ đệm, getline lần đầu tiên sẽ đọc dòng trống.
• Xử lý chuỗi rỗng hoặc chỉ toàn khoảng trắng: Code cần kiểm tra độ dài chuỗi trước khi truy cập s[0] để tránh lỗi runtime.
• Chỉ sửa casing mà không xử lý khoảng trắng thừa (như Solution 1): Kết quả đầu ra có thể vẫn chứa nhiều khoảng trắng hoặc khoảng trắng ở đầu/cuối, vi phạm yêu cầu đề bài.