在 C++ 中为给定列表中的每个单词查找最短的唯一前缀

在这个问题中,我们得到了一个词数组 arr[]。我们的任务是为给定列表中的每个单词找到最短的唯一前缀。

让我们举个例子来理解这个问题,

输入

arr[] = {“learn”, “programming”, “code”}
输出结果
c leap lear p

解决方法

该问题的一个简单解决方案是查找单词的所有前缀。然后检查它是否是数组中任何其他单词的前缀。如果不是,请打印。

一种有效的方法是使用特里数据结构。我们将构建一个trie并存储所有单词。然后找到每个单词的访问频率,而inserting.using单词,我们将找到它到词根的路径,即前缀。我们将从频率为 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

以上是 在 C++ 中为给定列表中的每个单词查找最短的唯一前缀 的全部内容, 来源链接: utcz.com/z/317413.html

回到顶部