Luồng ký tự trong C++

Triển khai lớp StreamChecker với hai phương thức:

• StreamChecker(words): Khởi tạo cấu trúc dữ liệu với danh sách từ cho trước.
• query(letter): Trả về true nếu tồn tại k ≥ 1 sao cho k ký tự vừa truy vấn (từ cũ đến mới, bao gồm ký tự hiện tại) tạo thành một từ trong danh sách.

Ví dụ: word list = ["ce", "g", "lm"], truy vấn lần lượt [a,b,c,e,f,g,h,i,j,k,l,m] → trả về true tại e, g, m.

Giải thuật

1. Xây dựng Trie (cây tiền tố) từ danh sách từ, nhưng lưu ngược (từ cuối về đầu) để dễ dàng kiểm tra hậu tố.
2. Giữ danh sách waitList các nút Trie đang chờ khớp tiếp theo.
3. Mỗi lần query(x):
   • Tạo danh sách temp mới.
   • Nếu gốc có con x, thêm gốc vào waitList.
   • Duyệt waitList: nếu nút hiện tại có con x, di chuyển đến con đó, thêm vào temp, và kiểm tra isEnd.
   • Hoán đổi temp và waitList.
   • Trả về true nếu bất kỳ nút nào trong waitList có isEnd = true.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
struct Node {
    Node* child[26];
    bool isEnd;
    Node(){
        isEnd = false;
        for (int i = 0; i < 26; i++) child[i] = NULL;
    }
};
class StreamChecker {
public:
    Node* head;
    vector<Node*> waitList;
    void insertNode(Node* head, string& s){
        Node* curr = head;
        for (int i = 0; i < s.size(); i++) {
            char x = s[i];
            if (!curr->child[x - 'a']) curr->child[x - 'a'] = new Node();
            curr = curr->child[x - 'a'];
        }
        curr->isEnd = true;
    }
    StreamChecker(vector<string>& words){
        head = new Node();
        for (int i = 0; i < words.size(); i++) insertNode(head, words[i]);
    }
    bool query(char x){
        vector<Node*> temp;
        if (head->child[x - 'a']) waitList.push_back(head);
        bool ret = false;
        for (int i = 0; i < waitList.size(); i++) {
            Node* curr = waitList[i];
            if (curr->child[x - 'a']) {
                curr = curr->child[x - 'a'];
                temp.push_back(curr);
                ret |= curr->isEnd;
            }
        }
        swap(temp, waitList);
        return ret;
    }
};
int main(){
    vector<string> v = {"ce","g","lm"};
    StreamChecker ob(v);
    cout << (ob.query('a')) << endl;
    cout << (ob.query('b')) << endl;
    cout << (ob.query('c')) << endl;
    cout << (ob.query('e')) << endl;
    cout << (ob.query('f')) << endl;
    cout << (ob.query('g')) << endl;
    cout << (ob.query('h')) << endl;
    cout << (ob.query('i')) << endl;
    cout << (ob.query('j')) << endl;
    cout << (ob.query('k')) << endl;
    cout << (ob.query('l')) << endl;
    cout << (ob.query('m'));
}

Đầu vào

"ce","g","lm", query()

Đầu ra

0 0 0 1 0 1 0 0 0 0 0 1