Viết hoa chữ cái đầu mỗi từ

Nguồn: CLUE OJ Độ khó: Dễ Duyệt xâu toupper / tolower

Đề bài

Cho một xâu họ tên đã chuẩn hoá (gồm các từ chỉ chứa chữ cái tiếng Anh, hai từ liền nhau cách nhau đúng một dấu cách, không có dấu cách ở đầu và cuối xâu). Các chữ cái có thể đang viết hoa hoặc viết thường lẫn lộn.

Hãy in ra họ tên chuẩn: 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.

Dữ liệu vào:

Một dòng duy nhất là xâu họ tên $S$.

Kết quả:

In ra họ tên sau khi đã viết hoa chữ cái đầu của mỗi từ.

Giới hạn:

• $1 \le |S| \le 10^6$

Subtask:

• Subtask 1 (50% số điểm): $|S| \le 1000$.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

le thanh huy

Ví dụ 1 – output

Le Thanh Huy

Ví dụ 2 – input

VINH DINH

Ví dụ 2 – output

Vinh Dinh

• Ví dụ 2: các chữ cái không đứng đầu từ phải chuyển về chữ thường: VINH → Vinh.

Nguồn: phỏng theo bài "TÊN CHUẨN" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Bài làm quen với việc duyệt từng kí tự của xâu và đổi chữ hoa – chữ thường. Điểm mấu chốt: làm sao biết một kí tự là chữ đầu của một từ? Ghi chú: đề gốc chỉ nói "in hoa các kí tự đầu tiên của từ", nhưng ví dụ VINH DINH → Vinh Dinh cho thấy các chữ còn lại phải về chữ thường, nên mình ghi rõ điều này; đề gốc ghi "không quá dài", mình chốt $|S| \le 10^6$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngkí tự đứng sau dấu cáchLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–14 có $|S| \le 2 \cdot 10^5$, test 15–20 dài tới $10^6$ kí tự.

Test	Nội dung kiểm tra
1–2	Ví dụ của đề
3–11	Xâu ngắn: 1 chữ cái, từ viết hoa toàn bộ, hoa – thường lẫn lộn (nGUYEN vAN a)
12–20	Xâu sinh ngẫu nhiên tới $10^6$ kí tự, chữ hoa – thường lẫn lộn; test 20 toàn từ 1 chữ cái – nối xâu kiểu t = t + c bị quá thời gian

Ý tưởngChữ đầu từ = kí tự đầu xâu hoặc đứng ngay sau dấu cách

Vì xâu đã chuẩn hoá (mỗi hai từ cách nhau đúng một dấu cách, không có dấu cách ở đầu), kí tự s[i] là chữ đầu của một từ khi và chỉ khi:

i == 0  hoặc  s[i - 1] == ' '

Khi đó ta viết hoa nó bằng toupper(s[i]); mọi chữ cái khác ta viết thường bằng tolower(s[i]) (dấu cách đi qua tolower vẫn là dấu cách).

Đừng quên viết thường phần còn lại

Nếu chỉ viết hoa chữ đầu thì VINH vẫn là VINH chứ không thành Vinh. Mỗi kí tự phải được xử lý: hoặc viết hoa, hoặc viết thường.

Em nhập họ tên rồi bấm Tiếp để xem từng kí tự được xử lý:

Họ tên =

Ví dụ nhanh:

Lời giảiMột vòng for qua xâu

Đọc cả dòng bằng getline(cin, s) (C++) hoặc input() (Python) vì họ tên có dấu cách – cin >> s chỉ đọc được một từ.

C++▶ Chạy tay từng dòng codeDuyệt từng kí tự, viết hoa chữ đầu từ, viết thường phần còn lại.

Dữ liệu vào (stdin) – sửa thoải máile thanh huy

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. toupper/tolower chỉ đổi chữ cái; chữ đã đúng dạng thì giữ nguyên, nên không cần kiểm tra trước.
2. Python có sẵn s.title() nhưng nên tự viết vòng lặp để hiểu bản chất (và title() xử lý khác với kí tự đặc biệt).
3. Sửa trực tiếp trên s thay vì tạo xâu mới bằng t = t + c: phép t + c tạo một xâu mới dài bằng $t$ mỗi lần nên tổng cộng $O(n^2)$.

Không gian$O(|S|)$

Thời gian$O(|S|)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.027s. Bản Python đúng 20/20 test, chạy lâu nhất 0.280s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Chỉ viết hoa chữ đầu, không viết thường các chữ còn lại	7/20	sai test 2, 5, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19
Chỉ xét kí tự sau dấu cách, quên i == 0	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Đọc bằng cin >> s (chỉ được một từ)	3/20	sai test 1, 2, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Tạo xâu mới bằng t = t + c	14/20	sai test 15, 16, 17, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.027s	Full điểm
	Python	20/20	0.280s	Full điểm
Không viết thường	C++	7/20	–	Mất 13 test
Quên i = 0	C++	0/20	–	Mất 20 test
cin >> s	C++	3/20	–	Mất 17 test
t = t + c	C++	14/20	–	Mất 6 test

Ghi chú của mình: với xâu đã chuẩn hoá, "chữ đầu từ" ⇔ "đầu xâu hoặc ngay sau dấu cách". Mẹo nhìn kí tự đứng trước s[i-1] sẽ còn dùng rất nhiều trong các bài xử lý từ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇