সি++-এ দেওয়া শব্দের তালিকা থেকে প্রতিটি শব্দের জন্য সর্বোচ্চ ছোট ইউনিক প্রিফিক্স (Shortest Unique Prefix) বের করা

এই সমস্যাতে, আমাদের শব্দের একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হলো প্রদত্ত তালিকায় প্রতিটি শব্দের জন্য সর্বোচ্চ ছোট ইউনিক প্রিফিক্স (shortest unique prefix) বের করা।

উদাহরণ দিয়ে সমস্যা বোঝা যাক,

ইনপুট

arr[] = {"learn", "programming", "code"}

আউটপুট

c leap lear p

সমাধানের পদ্ধতি

এই সমস্যার একটি সহজ সমাধান হলো শব্দের সব প্রিফিক্স (prefix) বের করা। তারপর চেক করা এটি অ্যারেতে অন্য কোনো শব্দের প্রিফিক্স কিনা। যদি না হয়, তবে সেটি প্রিন্ট করা।

একটি দক্ষ পদ্ধতি হলো ট্রাই (Trie) ডেটা স্ট্রাকচার ব্যবহার করা। আমরা একটি ট্রাই কনস্ট্রাক্ট করব এবং সব শব্দ সংরক্ষণ করব। ইনসার্ট করার সময় প্রতিটি শব্দের জন্য ভিজিট করার ফ্রিকোয়েন্সি (frequency) সংরক্ষণ করব। শব্দগুলো ব্যবহার করে রুট পর্যন্ত এর পথ বের করব যা হলো প্রিফিক্স। ফ্রিকোয়েন্সি ১ वाली নোড থেকে সব প্রিফিক্স প্রিন্ট করব।

সমাধান কোড:

উদাহরণ

#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; 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<<prefixChar<<endl;
        return;
    }
    for (int i=0; ichild[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