สตรีมของตัวละครใน C++

สมมติว่าเราต้องการใช้คลาส StreamChecker ดังนี้ -

• StreamChecker(words) - นี่คือตัวสร้าง ซึ่งเริ่มต้นโครงสร้างข้อมูลด้วยคำที่กำหนด

• query(letter) − ค่านี้คืนค่าเป็นจริงเมื่อสำหรับ k>=1 ตัว k ตัวสุดท้ายที่ถูกสืบค้น (เรียงจากเก่าสุดไปหาใหม่สุด รวมถึงตัวอักษรนี้ที่เพิ่งสอบถาม) สะกดคำใดคำหนึ่งในรายการที่กำหนด

ดังนั้น หากอินพุตเป็นเหมือนรายการคำ =["ce", "g", "lm"] ให้เรียกใช้แบบสอบถามหลายครั้งสำหรับ [a,b,c,e,f,g,h,i,j,k ,l,m] จากนั้นผลลัพธ์จะเป็นจริงสำหรับ e, g, m และเป็นเท็จสำหรับตัวอื่นๆ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดโครงสร้างโหนด มีอาร์เรย์ 26 โหนด และแฟล็ก isEnd

• เริ่มแรก isEnd เป็นเท็จ และอาร์เรย์ลูกจะเต็มไปด้วยค่า null

• กำหนดส่วนหัวของโหนด

• สร้างอาร์เรย์ของโหนด waitList

• กำหนดฟังก์ชัน insertNode() นี้จะใช้หัว s,

  • curr :=หัว

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • x :=s[i]

    • ถ้าลูก[x - 'a'] ของสกุลเงินไม่เป็นโมฆะ −

      • curr.child[x - 'a'] =สร้างโหนดโหนดใหม่

    • curr :=curr.child[x - 'a']

  • isEnd of curr :=true

• จากตัวเริ่มต้นให้ทำสิ่งนี้

  • head :=สร้างโหนดใหม่

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของคำ อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • insertNode(หัว, คำ[i])

  • curr :=หัว

• กำหนดฟังก์ชัน query() ซึ่งจะใช้เวลา x

  • ทำให้หนึ่งอาร์เรย์ของโหนดชั่วคราว

  • ถ้า head.child[x - 'a'] แล้ว −

    • ใส่ส่วนหัวที่ส่วนท้ายของ waitList

  • ret :=เท็จ

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ waitList ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • curr :=waitList[i]

    • ถ้า curr.child[x - 'a'] แล้ว

      • curr :=child[x - 'a'] ของสกุลเงิน

      • ใส่ curr ที่จุดสิ้นสุดของอุณหภูมิ

      • ret :=ret OR คือจุดสิ้นสุดของสกุลเงิน

  • สลับ (ชั่วคราว, waitList)

  • รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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]);
      }
      Node* curr = head;
   }
   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;
   }
};
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'));
}

อินพุต

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

ผลลัพธ์

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