好资源导航 » 文章资讯 » 在 C++ 中为给定列表中的每个单词查找最短的唯一前缀

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

2023-06-16 12:27:06 69

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

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

输入

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

输出结果

c leap lear p

解决方法

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

一种有效的方法是使用特里数据结构。我们将构建一个trie并存储所有单词。然后找到每个单词的访问频率，而inserting.using单词，我们将找到它到词根的路径，即前缀。我们将从频率为1的节点开始打印所有前缀。

程序来说明我们的解决方案的工作，

示例

#include
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; ichild[i] = NULL;
   return newNode;
}
void insert(struct trieNode *root, string str) {
   int len = str.length();
   struct trieNode *pCrawl = root;
   for (int level = 0; levelchild[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<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输出结果All Shortest unique prefix for every words in a given list are −
c
leap
lear
p

返回顶部
514930285
czq8825@qq.com

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

输入

解决方法

示例

热门推荐

随机推荐