C++에서 배열의 문자를 사용하여 가능한 모든 유효한 단어 인쇄

이 문제의 경우 단어 집합과 문자 배열이 주어지고 해당 단어가 가능한지 여부를 해당 배열의 문자를 사용하여 확인해야 합니다.

문제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

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

설명 − 단어 중 주어진 문자를 포함하는 단어는 - go, hog 및 rest는 char 배열에 문자를 포함하지 않습니다.

이 문제를 해결하기 위해 우리는 tri 데이터 구조를 사용할 것입니다. 이 시도에서는 모든 단어를 저장한 다음 배열의 문자를 기반으로 tri에서 단어를 검색합니다.

예

#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