इस समस्या में, हमें 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. है