मान लीजिए हम StreamChecker क्लास को निम्नानुसार लागू करना चाहते हैं:
StreamChecker(words) - यह कंस्ट्रक्टर है, जो दिए गए शब्दों के साथ डेटा संरचना को इनिशियलाइज़ करता है।
query(letter) - यह तब true लौटाता है जब कुछ k >= 1 के लिए, अंतिम k क्वेरी किए गए वर्ण (पुराने से नए क्रम में, इस नए क्वेरी किए गए अक्षर सहित) दी गई सूची में से किसी एक शब्द को स्पेल करते हैं।
उदाहरण के लिए, यदि इनपुट शब्द सूची = ["ce", "g", "lm"] है, तो [a,b,c,e,f,g,h,i,j,k,l,m] के लिए कई बार क्वेरी कॉल करें, तो आउटपुट e, g, m के लिए true होगा, और बाकी के लिए false।
हल करने का दृष्टिकोण
हम एक ट्राई (प्रीफिक्स ट्री) का उपयोग करते हैं जहां शब्दों को उल्टे क्रम में संग्रहीत किया जाता है, और सक्रिय नोड्स की एक प्रतीक्षा सूची बनाए रखते हैं:
26 बच्चों और isEnd फ्लैग के साथ एक नोड संरचना परिभाषित करें
सभी शब्दों को उल्टे क्रम में ट्राई में डालें
प्रत्येक क्वेरी के लिए, प्रतीक्षा सूची में सभी सक्रिय नोड्स को नए वर्ण के साथ अपडेट करें
यदि कोई नोड शब्द के अंत तक पहुंचता है, तो true लौटाएं
अगली क्वेरी के लिए प्रतीक्षा सूची अपडेट करें
उदाहरण
#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'));
return 0;
}
इनपुट
"ce","g","lm", query()
आउटपुट
0 0 0 1 0 1 0 0 0 0 0 1