C++-এ শব্দ সংক্ষিপ্তিকরণ (Word Abbreviation)

n সংখ্যক ইউনিক স্ট্রিং দেওয়া আছে। প্রতিটি শব্দের জন্য ন্যূনতম সম্ভাব্য সংক্ষিপ্তরূপ তৈরি করতে হবে নিম্নলিখিত নিয়মাবলী অনুসরণ করে:

• প্রথম অক্ষর, তারপর সংক্ষিপ্ত করা অক্ষরের সংখ্যা, তারপর শেষ অক্ষর।
• যদি একাধিক শব্দের একই সংক্ষিপ্তরূপ হয়, তবে konflikt দূর করতে বড় প্রিফিক্স ব্যবহার করতে হবে যতক্ষণ না প্রতিটি শব্দের সংক্ষিপ্তরূপ ইউনিক হয়ে যায়।
• যদি সংক্ষিপ্তরূপ শব্দকে ছোট করে না, তবে মূল শব্দটিই রাখতে হবে।

ইনপুট ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] হলে আউটপুট ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]।

সমাধানের ধাপসমূহ

• Node কাঠামো সংজ্ঞায়িত করুন (cnt এবং ২৬টি child node)
• freeNode() ফাংশন: মেমরি মুক্ত করতে
• insertNode() ফাংশন: ট্রাইতে শব্দ যোগ করতে
• abbreviate() ফাংশন: ট্রাই থেকে সংক্ষিপ্তরূপ বের করতে
• wordsAbbreviation() ফাংশন:
  • প্রতিটি শব্দের প্রাথমিক সংক্ষিপ্তরূপ বের করুন
  • konflikt থাকলে ট্রাই তৈরি করে unik সংক্ষিপ্তরূপ বের করুন

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; ichild[i]);
        }
        delete head;
    }
    void insertNode(Node* node, string s){
        Node* curr = node;
        for (int i = 0; i < s.size(); i++) {
            char x = s[i];
            if (!node->child[x - 'a']) {
                node->child[x - 'a'] = new Node();
            }
            node = node->child[x - 'a'];
            node->cnt++;
        }
    }
    string abbreviate(Node* node, string s){
        string ret = "";
        Node* curr = node;
        for (int i = 0; i < s.size(); i++) {
            char x = s[i];
            curr = curr->child[x - 'a'];
            if (curr->cnt == 1) {
                int rem = s.size() - (i + 2);
                ret = rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back();
                break;
            }
        }
        return ret;
    }
    vector<string> wordsAbbreviation(vector<string>& dict) {
        int n = dict.size();
        vector<string> ret(n);
        map<string, vector<int> > m;
        for (int i = 0; i < n; i++) {
            string word = dict[i];
            int rem = word.size() - 2;
            string x = rem <= 1 ? word : word.front() + to_string(rem) + word.back();
            m[x].push_back(i);
            ret[i] = x;
        }
        Node* head;
        map<string, vector<int> >::iterator it = m.begin();
        while (it != m.end()) {
            if (it->second.size() <= 1) {
                it++;
                continue;
            }
            head = new Node();
            for (int i = 0; i < it->second.size(); i++) {
                int idx = it->second[i];
                insertNode(head, dict[idx]);
            }
            for (int i = 0; i < it->second.size(); i++) {
                int idx = it->second[i];
                ret[idx] = abbreviate(head, dict[idx]);
            }
            freeNode(head);
            it++;
        }
        return ret;
    }
};
int main(){
    Solution ob;
    vector<string> v = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
    print_vector(ob.wordsAbbreviation(v));
}

ইনপুট

{"like","god","internal","me","internet","interval","intension","face","intrusion"}

আউটপুট

[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n, ]