สตรีมตัวอักษรใน C++ (StreamChecker)

คำอธิบายปัญหา

ออกแบบคลาส StreamChecker ที่รองรับ 2 การดำเนินการ:

• StreamChecker(words) - คอนสตรัคเตอร์ เริ่มต้นด้วยลิสต์คำ
• query(letter) - คืน true หากตัวอักษร k ตัวล่าสุด (จากเก่าสู่ใหม่ รวมตัวที่เพิ่ง query) สร้างคำใดคำหนึ่งในลิสต์ได้

ตัวอย่าง

words = ["ce", "g", "lm"]
query: a,b,c,e,f,g,h,i,j,k,l,m
ผลลัพธ์: true ที่ e, g, m (false สำหรับตัวอื่น)

แนวทางแก้ปัญหา: Trie + Active Node Tracking

1. สร้าง Trie จากคำทั้งหมด (เก็บแบบปกติ ไม่ต้องกลับ)
2. เก็บรายการโหนดที่กำลัง "รอ" ตัวอักษรถัดไป (waitList)
3. เมื่อ query ตัวอักษร x:
   • ถ้า root มีลูก x ให้เพิ่ม root เข้า waitList
   • วนลูป waitList: ลองเดินต่อจากโหนดปัจจุบันด้วย x
   • ถ้าเดินได้ ให้เพิ่มโหนดถัดไปเข้า temp list และเช็ค isEnd
   • สลับ temp กับ waitList

โครงสร้างโหนด

struct Node {
    Node* child[26];
    bool isEnd;
    Node() { isEnd=false; fill(begin(child), end(child), nullptr); }
};

ตัวอย่างโค้ด C++

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

struct Node {
    Node* child[26];
    bool isEnd;
    Node() { isEnd=false; fill(begin(child), end(child), nullptr); }
};

class StreamChecker {
    Node* head;
    vector<Node*> waitList;
    
    void insertNode(Node* head, string& s) {
        Node* cur = head;
        for(char c : s) {
            int idx = c-'a';
            if(!cur->child[idx]) cur->child[idx] = new Node();
            cur = cur->child[idx];
        }
        cur->isEnd = true;
    }
    
public:
    StreamChecker(vector<string>& words) {
        head = new Node();
        for(auto& w : words) insertNode(head, w);
    }
    
    bool query(char x) {
        vector<Node*> temp;
        int idx = x-'a';
        if(head->child[idx]) waitList.push_back(head);
        
        bool ret = false;
        for(Node* cur : waitList) {
            if(cur->child[idx]) {
                cur = cur->child[idx];
                temp.push_back(cur);
                ret |= cur->isEnd;
            }
        }
        waitList.swap(temp);
        return ret;
    }
};

ความซับซ้อน

• สร้าง: O(รวมความยาวคำ)
• query: O(จำนวนโหนดใน waitList) ≤ O(รวมความยาวคำ)
• พื้นที่: O(รวมความยาวคำ)