सी ++ में वर्णों की धारा

मान लीजिए कि हम StreamChecker वर्ग को इस प्रकार लागू करना चाहते हैं -

• StreamChecker(words) - यह कंस्ट्रक्टर है, यह दिए गए शब्दों के साथ डेटा संरचना को इनिशियलाइज़ करता है।

• query(letter) - यह तब सही होता है जब कुछ k>=1 के लिए, अंतिम k वर्णों के लिए पूछताछ की जाती है (सबसे पुराने से नवीनतम तक, इस पत्र को शामिल करने के क्रम में) दी गई सूची में से किसी एक शब्द की वर्तनी होती है।

इसलिए, यदि इनपुट शब्द सूची =["सीई", "जी", "एलएम"] की तरह है, तो [ए, बी, सी, ई, एफ, जी, एच, आई, जे, के लिए कई बार कॉल करें ,l,m], तो आउटपुट e, g, m, और अन्य के लिए गलत होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक नोड संरचना को परिभाषित करें, 26 नोड्स की एक सरणी है, और अंत ध्वज है

• प्रारंभ में isEnd गलत है, और चाइल्ड सरणी शून्य से भरी हुई है।

• नोड हेड परिभाषित करें

• नोड्स की एक सरणी प्रतीक्षा सूची बनाएं

• एक फ़ंक्शन इन्सर्टनोड () को परिभाषित करें, यह सिर लेगा, s,

  • वक्र:=सिर

  • इनिशियलाइज़ करने के लिए i:=0, जब i

    • एक्स:=एस [i]

    • अगर बच्चे [x - 'a'] का curr शून्य नहीं है, तो -

      • curr.child[x - 'a'] =एक नया नोड नोड बनाएं

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

  • isEnd of curr :=true

• प्रारंभकर्ता से ऐसा करें

  • सिर :=एक नया नोड बनाएं

  • इनिशियलाइज़ i :=0 के लिए, जब i <शब्दों का आकार, अपडेट (i 1 से बढ़ाएँ), करें -

    • insertNode(सिर, शब्द[i])

  • वक्र:=सिर

• फ़ंक्शन क्वेरी () को परिभाषित करें, इसमें x लगेगा,

  • नोड्स अस्थायी की एक सरणी बनाएं

  • अगर head.child[x - 'a'], तो -

    • प्रतीक्षा सूची के अंत में सिर डालें

  • रिट :=असत्य

  • प्रारंभ करने के लिए मैं:=0, जब मैं <प्रतीक्षा सूची का आकार, अद्यतन (मैं 1 से बढ़ाएँ), करते हैं -

    • वक्र:=प्रतीक्षा सूची [i]

    • अगर curr.child[x - 'a'], तो

      • curr :=बच्चा [x - 'a'] curr का

      • अस्थायी के अंत में curr डालें

      • ret :=ret OR isEnd of curr

  • स्वैप (अस्थायी, प्रतीक्षासूची)

  • वापसी रिट

#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