এই সমস্যায়, আমাদের 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
