Hiểu bài toán

Cho một đoạn văn bản chỉ gồm các chữ cái Latin và dấu chấm '.' dùng để phân cách giữa các từ. Nhiệm vụ là đếm số lượng từ có trong đoạn văn bản đó. Một từ được định nghĩa là một chuỗi các ký tự chữ cái liên tiếp nhau, được ngăn cách bởi dấu chấm. Văn bản đầu vào luôn khác rỗng và có độ dài tối đa 100 ký tự. Ví dụ: 'Dai.hoc.Nha.Trang.' có 4 từ là 'Dai', 'hoc', 'Nha', 'Trang'.

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

Cách Xử lý chuỗi theo từng từ (Tokenization)

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s; cin >> s;
    vector<string> v;
    int i = 0;
    while(i < s.length()){
        if(s[i] != '.'){
            string a;
            while(s[i] != '.' && i < s.length()){
                a += s[i];
                i++;
            }
            v.push_back(a);
        } else i++;
    }
    cout << v.size();
}

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

Cách tiếp cận này sử dụng một vòng lặp để duyệt qua chuỗi. Khi gặp một ký tự không phải dấu chấm, nó bắt đầu một từ mới và tiếp tục lặp để thêm các ký tự vào từ đó cho đến khi gặp dấu chấm hoặc kết thúc chuỗi. Từ hoàn chỉnh được lưu vào một vector. Cuối cùng, kích thước của vector chính là số từ. Phương pháp này mô phỏng quá trình tách từ (tokenization) một cách rõ ràng.

Cách Đếm điểm bắt đầu của từ (Edge Detection)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    int n = s.size();
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] != '.' && (i == 0 || s[i-1] == '.')) {
            ++cnt;
        }
    }
    cout << cnt << '\n';
    return 0;
}

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

Cách tiếp cận này tối ưu hơn về mặt bộ nhớ. Thay vì lưu trữ các từ, ta chỉ cần đếm số lượng từ. Một từ được coi là bắt đầu tại chỉ số i nếu ký tự tại i không phải dấu chấm và nó nằm ở vị trí đầu tiên của chuỗi (i == 0) hoặc ngay sau một dấu chấm (s[i-1] == '.'). Bằng cách đếm các điểm bắt đầu này, ta có được kết quả mà không cần lưu thêm dữ liệu thừa.

Cách Sử dụng cờ trạng thái (State Flag)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    int wordCount = 0;
    bool inWord = false;

    for (char c : s) {
        if (isalpha(c)) {
            if (!inWord) {
                wordCount++;
                inWord = true;
            }
        } else if (c == '.') {
            inWord = false;
        }
    }
    cout << wordCount;
    return 0;
}

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

Phương pháp này sử dụng một biến boolean (cờ) để theo dõi xem trình duyệt đang ở trong một từ hay không. Ban đầu, cờ là false. Khi gặp một ký tự chữ cái mà cờ đang false, ta tăng biến đếm và bật cờ lên true. Khi gặp dấu chấm, ta tắt cờ xuống false. Điều này đảm bảo rằng chỉ có ký tự đầu tiên của mỗi từ được đếm.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng cách đếm số lượng 'điểm bắt đầu' của các từ (ký tự không phải dấu chấm và là ký tự đầu tiên hoặc theo sau một dấu chấm).
• Có thể tối ưu bộ nhớ bằng cách chỉ đếm số lượng thay vì lưu trữ các từ vào một cấu trúc dữ liệu.

Lỗi thường gặp

• Quên xử lý ký tự kết thúc chuỗi (null terminator) hoặc độ dài chuỗi, dẫn đến lỗi truy cập ngoài biên.
• Xử lý sai các trường hợp đặc biệt như chuỗi kết thúc bằng dấu chấm hoặc nhiều dấu chấm liên tiếp.