Hướng dẫn giải của Đếm khoảng trắng trong chuỗi
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu đếm số lượng 'khoảng trắng' trong chuỗi. Một khoảng trắng được định nghĩa là một đoạn liên tiếp các ký tự dấu cách ('space'). Ví dụ, trong chuỗi 'abc xyz ab', có hai khoảng trắng: một khoảng ba dấu cách giữa 'abc' và 'xyz', và một khoảng một dấu cách giữa 'xyz' và 'ab'. Chuỗi đầu vào có thể chứa các ký tự chữ cái, số, và dấu cách. Cần xử lý T chuỗi.
Các cách tiếp cận
Cách Duyệt và Bỏ qua (Skip and Count)
#include <stdio.h>
#include <string.h>
int main() {
int T;
scanf("%d", &T);
getchar(); // Bỏ ký tự newline sau số T
while (T--) {
char s[1005];
fgets(s, 1005, stdin);
int cnt = 0;
int i = 0;
int len = strlen(s);
// Bỏ qua dấu cách ở đầu chuỗi (nếu có)
while (i < len && s[i] == ' ') i++;
for (; i < len; i++) {
if (s[i] == ' ') {
cnt++; // Phát hiện bắt đầu một khoảng trắng mới
// Bỏ qua tất cả các dấu cách liên tiếp sau đó
while (i < len && s[i] == ' ') i++;
}
}
printf("%d\n", cnt);
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Khởi tạo biến đếm. Duyệt qua từng ký tự của chuỗi. Khi gặp một dấu cách, ta tăng biến đếm lên 1 và dùng vòng lặp lồng để bỏ qua tất cả các dấu cách tiếp theo cho đến khi gặp ký tự không phải dấu cách. Cách này đảm bảo mỗi khối khoảng trắng chỉ được đếm một lần duy nhất.
Cách Đếm điểm đầu (Edge Detection)
#include <stdio.h>
#include <string.h>
int main() {
int T;
scanf("%d", &T);
getchar();
while (T--) {
char s[1005];
fgets(s, 1005, stdin);
int count = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
// Nếu là dấu cách AND (là ký tự đầu tiên HOẶC ký tự trước đó không phải dấu cách)
if (s[i] == ' ' && (i == 0 || s[i-1] != ' ')) {
count++;
}
}
printf("%d\n", count);
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Phương pháp này kiểm tra điều kiện để đánh dấu một khoảng trắng mới bắt đầu. Một khoảng trắng bắt đầu tại vị trí i nếu s[i] là dấu cách và s[i-1] không phải là dấu cách (hoặc i bằng 0). Logic này đếm chính xác số lượng các khối khoảng trắng.
Cách Thay thế và Đếm (Replace and Count)
#include <stdio.h>
#include <string.h>
int main() {
int T;
scanf("%d", &T);
getchar();
while (T--) {
char s[1005];
fgets(s, 1005, stdin);
int len = strlen(s);
// Chuẩn hóa: Bỏ dấu cách đầu và cuối chuỗi để tránh đếm nhầm
// (Phần này logic hơi rủi ro nếu dùng pointer, nên dùng mảng phụ hoặc logic kiểm tra)
// Ở đây ta dùng logic đơn giản: duyệt mảng và sửa đổi trực tiếp
int count = 0;
int is_space = 0; // Biến cờ để theo dõi đang ở trong khoảng trắng hay không
for (int i = 0; i < len; i++) {
if (s[i] == ' ') {
if (!is_space) {
count++;
is_space = 1;
}
// Đánh dấu để loại bỏ (hoặc coi như đã xử lý)
// Hoặc đơn giản là dùng logic state machine
} else {
is_space = 0;
}
}
printf("%d\n", count);
}
return 0;
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Sử dụng biến cờ (state) để theo dõi trạng thái. Nếu gặp dấu cách mà trước đó chưa phải dấu cách (cờ bằng 0), ta tăng biến đếm và bật cờ lên. Nếu gặp ký tự thường, tắt cờ. Đây là cách tiếp cận state-machine.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N) | O(N) | Duyệt và Bỏ qua (Skip and Count) |
| 2 | O(N) | O(N) | Đếm điểm đầu (Edge Detection) |
| 3 | O(N) | O(N) | Thay thế và Đếm (Replace and Count) |
Bài học kinh nghiệm
- Bài toán thực chất là đếm số block (khối) dấu cách liên tiếp nhau.
- Cần phân biệt giữa việc đếm số lượng dấu cách đơn lẻ và đếm số lượng các đoạn/dải dấu cách.
Lỗi thường gặp
- Quên xử lý ký tự newline '\n' cuối chuỗi do hàm
fgetsđọc vào. Ký tự này có thể không phải là dấu cách theo yêu cầu bài toán nhưng có thể gây nhiễu logic nếu không xử lý đúng (ví dụ:fgetsthường để lại '\n'). - Đếm sai nếu chuỗi bắt đầu hoặc kết thúc bằng dấu cách.
- Duyệt vòng lặp trong khi đang sửa đổi chỉ số vòng lặp (như Solution 1) có thể gây ra lỗi tràn bộ nhớ hoặc bỏ sót ký tự nếu không kiểm tra biên kỹ.
Bình luận