Hướng giải của Tập Từ Vựng Cây Tiền Tố

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu mô phỏng 3 thao tác cơ bản trên cây tiền tố (Trie):

  1. Insert (Thêm từ): Bắt đầu từ gốc, đi theo các ký tự của từ. Nếu đường đi chưa có thì tạo node mới.
  2. Search (Tìm từ chính xác): Đi theo các ký tự của từ. Nếu không đi tiếp được thì trả về false. Nếu đi hết từ, kiểm tra cờ kết thúc isEnd.
  3. StartsWith (Tìm tiền tố): Đi theo các ký tự của tiền tố. Nếu đi hết tiền tố thành công, trả về true (không cần kiểm tra isEnd).

Độ phức tạp thời gian cho mỗi thao tác là \(O(|S|)\) với \(|S|\) là độ dài xâu.

Mã nguồn C++ mẫu

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

struct TrieNode {
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEnd = false;
    }
};

struct Trie {
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            int idx = c - 'a';
            if (cur->children[idx] == nullptr) {
                cur->children[idx] = new TrieNode();
            }
            cur = cur->children[idx];
        }
        cur->isEnd = true;
    }

    bool search(const string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            int idx = c - 'a';
            if (cur->children[idx] == nullptr) return false;
            cur = cur->children[idx];
        }
        return cur->isEnd;
    }

    bool startsWith(const string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            int idx = c - 'a';
            if (cur->children[idx] == nullptr) return false;
            cur = cur->children[idx];
        }
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    if (!(cin >> q)) return 0;

    Trie trie;
    while (q--) {
        int t;
        string s;
        cin >> t >> s;
        if (t == 1) {
            trie.insert(s);
        } else if (t == 2) {
            cout << (trie.search(s) ? "YES" : "NO") << "\n";
        } else {
            cout << (trie.startsWith(s) ? "YES" : "NO") << "\n";
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.