คำอธิบายปัญหา
ในปัญหานี้ เราได้รับชุดคำ (set of words) และอาร์เรย์ของตัวอักษร และเราต้องตรวจสอบว่าคำเหล่านั้นเป็นไปได้โดยใช้ตัวอักษรของอาร์เรย์หรือไม่
ลองดูตัวอย่างเพื่อเข้าใจปัญหาให้ดีขึ้น:
Input : words[] : {'go' , 'hi' , 'run' , 'on' , 'hog' , 'gone'} Char[] : {'a' , 'o' , 'h' , 'g'} Output : go , hog.คำอธิบาย – จากคำต่างๆ คำที่มีตัวอักษรจากอาร์เรย์ที่กำหนดคือ go, hog ส่วนที่เหลือไม่ได้รวมตัวอักษรใน char array
เพื่อแก้ปัญหานี้ เราจะใช้ trie data structure ใน trie นี้ เราจะเก็บคำทั้งหมด และค้นหาคำใน 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
