इस समस्या के कारण, हमें शब्दों का एक सेट और वर्णों की एक सरणी दी गई है और हमें यह जांचना है कि क्या सरणी के वर्णों का उपयोग करके शब्द संभव हैं।
आइए समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
Input : words[] : {‘go’ , ‘hi’ , ‘run’ , ‘on’ , ‘hog’ , ‘gone’}
Char[] : {‘a’ , ‘o’ , ‘h’ , ‘g’}
Output : go , hog. स्पष्टीकरण - शब्दों में से, जिन शब्दों में दिए गए वर्ण हैं, वे हैं - गो, हॉग और रेस्ट में वर्ण सरणी में वर्ण शामिल नहीं हैं।
इस समस्या को हल करने के लिए, हम ट्राई डेटा संरचना का उपयोग करेंगे। इस ट्राई में, हम सभी शब्दों को स्टोर करेंगे और फिर सरणी के अक्षरों के आधार पर शब्दों को ट्राई में खोजेंगे।
उदाहरण
#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