C++の特定のリスト内のすべての単語の最短の一意のプレフィックスを検索します

この問題では、一連の単語arr[]が与えられます。私たちのタスクは、指定されたリスト内のすべての単語の最短の一意のプレフィックスを見つけることです。

問題を理解するために例を見てみましょう

入力

arr[] = {“learn”, “programming”, “code”}

出力

c leap lear p

ソリューションアプローチ

この問題の簡単な解決策は、単語のすべての接頭辞を見つけて、それが配列内の他の単語の接頭辞であるかどうかを確認することです。そうでない場合は、印刷してください。

効率的なアプローチ トライデータ構造を使用することです。トライを作成し、すべての単語を保存します。次に、挿入中に各単語にアクセスする頻度を見つけます。単語を使用して、接頭辞であるルートへのパスを見つけます。頻度1のノードから始まるすべてのプレフィックスを出力します。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
#define MAX 256
struct trieNode {
   struct trieNode *child[MAX];
   int freq;
};
struct trieNode *newTrieNode(void){
   struct trieNode *newNode = new trieNode;
   newNode->freq = 1;
   for (int i = 0; i<MAX; i++)
      newNode->child[i] = NULL;
   return newNode;
}
void insert(struct trieNode *root, string str) {
   int len = str.length();
   struct trieNode *pCrawl = root;
   for (int level = 0; level<len; level++) {
      int index = str[level];
      if (!pCrawl->child[index])
         pCrawl->child[index] = newTrieNode();
      else
         (pCrawl->child[index]->freq)++;
      pCrawl = pCrawl->child[index];
   }
}
void findShortestUniquePrefixRec(struct trieNode *root, char prefixChar[], int ind) {
   if (root == NULL)
      return;
   if (root->freq == 1) {
      prefixChar[ind] = '\0';
      cout<<prefixChar<<endl;
      return;
   }
   for (int i=0; i<MAX; i++) {
      if (root->child[i] != NULL) {
         prefixChar[ind] = i;
         findShortestUniquePrefixRec(root->child[i], prefixChar, ind+1);
      }
   }
}
void findShortestUniquePrefix(string arr[], int n) {
   struct trieNode *root = newTrieNode();
   root->freq = 0;
   for (int i = 0; i<n; i++)
      insert(root, arr[i]);
   char prefixChar[250];
   findShortestUniquePrefixRec(root, prefixChar, 0);
}
int main() {
   string arr[] = {"learn", "programming", "code", "leap"};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"All Shortest unique prefix for every words in a given list are : \n";
   findShortestUniquePrefix(arr, n);
   return 0;
}

出力

All Shortest unique prefix for every words in a given list are −
c
leap
lear
p