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