Tìm tiền tố duy nhất ngắn nhất cho mỗi từ trong danh sách nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng các từ arr []. Nhiệm vụ của chúng tôi là tìm tiền tố duy nhất ngắn nhất cho mỗi từ trong danh sách đã cho.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

c leap lear p

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tìm tất cả các tiền tố của từ và sau đó kiểm tra xem nó có phải là tiền tố của bất kỳ từ nào khác trong mảng hay không. Nếu không, hãy in nó.

Một cách tiếp cận hiệu quả là sử dụng cấu trúc dữ liệu trie. Chúng tôi sẽ tạo một trie và lưu trữ tất cả các từ. Sau đó, tìm tần suất truy cập cho mỗi từ trong khi chèn. Sử dụng các từ đó, chúng ta sẽ tìm thấy đường dẫn đến gốc của nó là tiền tố. Chúng tôi sẽ in tất cả các tiền tố bắt đầu từ nút có tần số 1.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

Đầu ra

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