এই সমস্যায়, আমাদেরকে শব্দের একটি সেট এবং অক্ষরের একটি অ্যারে দেওয়া হয়েছে এবং অ্যারের অক্ষর ব্যবহার করে শব্দগুলি সম্ভব কিনা তা পরীক্ষা করতে হবে৷
সমস্যাটি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
Input : words[] : {‘go’ , ‘hi’ , ‘run’ , ‘on’ , ‘hog’ , ‘gone’}
Char[] : {‘a’ , ‘o’ , ‘h’ , ‘g’}
Output : go , hog. ব্যাখ্যা − শব্দগুলির মধ্যে, প্রদত্ত অক্ষরগুলি ধারণ করে এমন শব্দগুলি হল - go, hog এবং rest অক্ষরগুলি অক্ষর অ্যারেতে অন্তর্ভুক্ত করে না৷
এই সমস্যা সমাধানের জন্য, আমরা trie ডেটা স্ট্রাকচার ব্যবহার করব। এই ট্রাইতে, আমরা সমস্ত শব্দ সংরক্ষণ করব এবং তারপর অ্যারের অক্ষরের উপর ভিত্তি করে ট্রাই-এ শব্দগুলি অনুসন্ধান করব৷
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define char_int(c) ((int)c - (int)'a')
#define int_to_char(c) ((char)c + (char)'a')
struct TrieNode{
TrieNode *Child[26];
bool leaf;
};
TrieNode *getNode(){
TrieNode * newNode = new TrieNode;
newNode->leaf = false;
for (int i =0 ; i< 26 ; i++)
newNode->Child[i] = NULL;
return newNode;
}
void insertnode(TrieNode *root, char *Key){
int n = strlen(Key);
TrieNode * pChild = root;
for (int i=0; i<n; i++){
int index = char_int(Key[i]);
if (pChild->Child[index] == NULL)
pChild->Child[index] = getNode();
pChild = pChild->Child[index];
}
pChild->leaf = true;
}
void vaidword(TrieNode *root, bool Hash[], string str){
if (root->leaf == true)
cout << str << "\t" ;
for (int K =0; K < 26; K++){
if (Hash[K] == true && root->Child[K] != NULL ){
char c = int_to_char(K);
vaidword(root->Child[K], Hash, str + c);
}
}
}
void PrintAllWords(char Arr[], TrieNode *root, int n){
bool Hash[26];
for (int i = 0 ; i < n; i++)
Hash[char_int(Arr[i])] = true;
TrieNode *pChild = root ;
string str = "";
for (int i = 0 ; i < 26 ; i++){
if (Hash[i] == true && pChild->Child[i] ){
str = str+(char)int_to_char(i);
vaidword(pChild->Child[i], Hash, str);
str = "";
}
}
}
int main(){
char Dict[][20] = {"go" , "hi" , "run" , "on" , "hog" , "gone"} ;
TrieNode *root = getNode();
int n = sizeof(Dict)/sizeof(Dict[0]);
for (int i=0; i<n; i++)
insertnode(root, Dict[i]);
char arr[] = {'a', 'o', 'g', 'h'} ;
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The words which are valid\t";
PrintAllWords(arr, root, N);
return 0;
} আউটপুট
The words which are valid go hog
