Hướng dẫn giải của Chuẩn hóa xâu

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giả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, thattinh777, 1000dayslearningcode, nquang2909

Editorial for chuanhoa: Chuẩn hóa xâu

Hiểu bài toán

Cho một xâu ký tự S chỉ chứa các ký tự chữ cái Latin và dấu cách (space). Nhiệm vụ là chuẩn hóa xâu S theo các quy tắc sau:

Xóa tất cả các dấu cách ở đầu xâu (nếu có).
Xóa tất cả các dấu cách ở cuối xâu (nếu có).
Thay thế mọi dãy dấu cách liên tiếp bằng duy nhất một dấu cách. Ví dụ: " abc xyz ab " được chuẩn hóa thành "abc xyz ab".

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

Cách Xử lý trực tiếp trên chuỗi (One-pass with Flags)

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

void chuanHoa(char *s) {
    int len = strlen(s);
    int i = 0, j = 0;
    int space = 1; // Cờ đánh dấu: 1 nếu đang ở trạng thái 'sau dấu cách', 0 nếu đang ở trạng thái 'sau ký tự'

    while (i < len) {
        if (isspace((unsigned char)s[i])) {
            if (!space) {
                s[j++] = ' ';
                space = 1;
            }
        } else {
            s[j++] = s[i];
            space = 0;
        }
        i++;
    }
    // Xóa dấu cách cuối cùng nếu có
    if (j > 0 && s[j - 1] == ' ') j--;
    s[j] = '\0';
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    getchar(); // Đọc ký tự newline sau số T
    char s[1005];
    for (int t = 0; t < T; t++) {
        if (!fgets(s, sizeof(s), stdin)) s[0] = '\0';
        s[strcspn(s, "\n")] = '\0'; // Xóa newline
        chuanHoa(s);
        printf("%s\n", s);
    }
    return 0;
}

Time Complexity: O(N)
Space Complexity: O(1) (Xử lý trực tiếp tại chỗ)

Thuật toán duyệt qua chuỗi một lần duy nhất. Sử dụng một biến boolean space để theo dõi trạng thái.

Nếu gặp ký tự bình thường: ghi vào vị trí j và đặt space = 0.
Nếu gặp dấu cách:
- Nếu trước đó là ký tự bình thường (space == 0): ghi một dấu cách vào vị trí j và đặt space = 1.
- Nếu trước đó là dấu cách (space == 1): bỏ qua. Sau vòng lặp, kiểm tra và loại bỏ dấu cách cuối cùng nếu chuỗi kết thúc bằng dấu cách.

Cách Xử lý Logic Đơn giản (Duyệt và Ghép)

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

int main() {
    int t;
    scanf("%d", &t);
    getchar();
    char str[1005];
    while (t--) {
        fgets(str, sizeof(str), stdin);
        int len = strlen(str);
        if (len > 0 && str[len - 1] == '\n') str[--len] = '\0';

        char result[1005];
        int res_idx = 0;
        int in_space = 0; // Trạng thái đang xử lý dấu cách
        int is_first = 1;  // Để kiểm tra dấu cách đầu tiên

        for (int i = 0; i < len; i++) {
            if (str[i] != ' ') {
                result[res_idx++] = str[i];
                in_space = 0;
            } else {
                if (!in_space) {
                    // Chỉ thêm dấu cách nếu không phải là ký tự đầu tiên của chuỗi mới
                    if (res_idx > 0) { 
                        result[res_idx++] = ' ';
                    }
                    in_space = 1;
                }
            }
        }
        // Xóa dấu cách cuối cùng nếu có
        if (res_idx > 0 && result[res_idx - 1] == ' ') res_idx--;
        result[res_idx] = '\0';
        printf("%s\n", result);
    }
    return 0;
}

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

Phương pháp này xây dựng một xâu mới result.

Duyệt từng ký tự trong xâu gốc.
Nếu là ký tự thường: thêm vào result.
Nếu là dấu cách: chỉ thêm vào result nếu dấu cách này là dấu cách đầu tiên trong dãy (thông qua cờ in_space) và result chưa rỗng (để tránh dấu cách đầu).
Cuối cùng, loại bỏ dấu cách cuối cùng nếu result kết thúc bằng dấu cách.

Cách Phương pháp Tách từ (Tokenize)

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

int main() {
    int t;
    scanf("%d", &t);
    getchar();
    while (t--) {
        char line[1005];
        if (fgets(line, sizeof(line), stdin) == NULL) continue;

        char *words[500];
        int count = 0;

        // Tách từ bằng strtok
        char *token = strtok(line, " \t\n\r");
        while (token != NULL) {
            words[count++] = token;
            token = strtok(NULL, " \t\n\r");
        }

        // In các từ
        for (int i = 0; i < count; i++) {
            printf("%s", words[i]);
            if (i < count - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

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

Sử dụng hàm strtok (hoặc tương tự) để chia xâu thành các từ riêng biệt dựa trên dấu cách.

Mảng words lưu trữ con trỏ tới các từ.
Sau khi tách xong, duyệt mảng và in các từ ra với dấu cách ngăn cách.

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

Cách tiếp cận	Time	Space	Tên
1	O(N)	O(1) (Xử lý trực tiếp tại chỗ)	Xử lý trực tiếp trên chuỗi (One-pass with Flags)
2	O(N)	O(N)	Xử lý Logic Đơn giản (Duyệt và Ghép)
3	O(N)	O(N)	Phương pháp Tách từ (Tokenize)

Bài học kinh nghiệm

Bài toán có thể giải quyết hiệu quả bằng cách duyệt qua chuỗi một lần (One-pass) hoặc sử dụng các hàm tiện ích có sẵn.
Cần phân biệt rõ ràng giữa việc xử lý 'dấu cách thừa' và 'dấu cách ở đầu/cuối'.

Lỗi thường gặp

Quên xử lý ký tự newline '\n' do hàm fgets đọc vào, dẫn đến sai lệch khi so sánh hoặc in ra.
Xử lý sai trường hợp chuỗi chỉ toàn dấu cách (kết quả phải là chuỗi rỗng).
Thêm một dấu cách ở đầu hoặc cuối chuỗi output do logic kiểm tra điều kiện不够严谨.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.