In tất cả các từ hợp lệ có thể sử dụng Các ký tự của mảng trong C ++

Trong vấn đề này, chúng ta được cung cấp một tập hợp các từ và một mảng ký tự và chúng ta phải kiểm tra xem các từ có thể sử dụng các ký tự của mảng hay không.

Hãy lấy một ví dụ để hiểu rõ vấn đề hơn -

Input : words[] : {‘go’ , ‘hi’ , ‘run’ , ‘on’ , ‘hog’ , ‘gone’}
   Char[] : {‘a’ , ‘o’ , ‘h’ , ‘g’}
Output : go , hog.

Giải thích - Ngoài các từ, các từ có chứa các ký tự đã cho là - go, hog và rest không bao gồm các ký tự trong mảng char.

Để giải quyết vấn đề này, chúng ta sẽ sử dụng cấu trúc dữ liệu trie. Trong trie này, chúng tôi sẽ lưu trữ tất cả các từ và sau đó tìm kiếm các từ trong trie dựa trên các chữ cái của mảng.

Ví dụ

#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;
}

Đầu ra

The words which are valid go hog