সমস্যা বিবরণ
StreamChecker ক্লাস বাস্তবায়ন করতে হবে যাতে দুটি ফাংশন থাকে:
- StreamChecker(words) — কনস্ট্রাক্টর, শব্দ들의 তালিকা দিয়ে ডেটা স্ট্রাকচার ইনিশিয়ালাইজ করে।
- query(letter) — true রিটার্ন করবে যদি শেষ kটি ক্যারেক্টার (পুরনো থেকে নতুন ক্রমে, বর্তমান লেটারসহ) দেওয়া শব্দগুলোর যেকোনো একটি বানাতে পারে।
উদাহরণ
শব্দ তালিকা = ["ce", "g", "lm"], কোয়েরি সিকোয়েন্স = [a,b,c,e,f,g,h,i,j,k,l,m] → আউটপুট: e, g, m-এ true, বাকিতে false।
সমাধান পদ্ধতি
- ট্রাই (Trie) ডেটা স্ট্রাকচার ব্যবহার করা হয়।
- প্রতিটি নোডে ২৬টি চাইল্ড পয়েন্টার এবং isEnd ফ্ল্যাগ থাকে।
- কোয়েরি সময় waitList-এ সক্রিয় ট্রাই নোডগুলো রাখা হয়।
- নতুন ক্যারেক্টার আসলে waitList আপডেট করা হয় এবং isEnd চেক করা হয়।
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 {
Node* head;
vector<Node*> waitList;
void insertNode(Node* head, string& s) {
Node* curr = head;
for (char x : s) {
if (!curr->child[x - 'a'])
curr->child[x - 'a'] = new Node();
curr = curr->child[x - 'a'];
}
curr->isEnd = true;
}
public:
StreamChecker(vector<string>& words) {
head = new Node();
for (auto& w : words) insertNode(head, w);
}
bool query(char x) {
vector<Node*> temp;
if (head->child[x - 'a']) waitList.push_back(head);
bool ret = false;
for (Node* curr : waitList) {
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);
string queries = "abcefghijklm";
for (char c : queries)
cout << ob.query(c) << " ";
return 0;
}ইনপুট ও আউটপুট
ইনপুট: "ce","g","lm", query()
আউটপুট: 0 0 0 1 0 1 0 0 0 0 0 1
