C++ এ শব্দ সংক্ষেপণ

ধরুন আমাদের কাছে n অনন্য স্ট্রিংগুলির একটি অ্যারে আছে, আমাদের নীচের নিয়মগুলি অনুসরণ করে প্রতিটি শব্দের জন্য ন্যূনতম সম্ভাব্য সংক্ষেপণ তৈরি করতে হবে৷

• প্রথম অক্ষর দিয়ে শুরু করে তারপর সংক্ষিপ্ত অক্ষর সংখ্যা, যার পরে শেষ অক্ষর।

• যদি আমরা কোনো দ্বন্দ্ব খুঁজে পাই এবং এটি একই সংক্ষেপে একাধিক শব্দ শেয়ার করে, তবে শব্দ থেকে সংক্ষেপে মানচিত্রটি অনন্য না হওয়া পর্যন্ত শুধুমাত্র প্রথম অক্ষরের পরিবর্তে একটি দীর্ঘ উপসর্গ ব্যবহার করা যেতে পারে।

• যখন সংক্ষেপণ শব্দটিকে ছোট করে না, তখন এটিকে আসল হিসাবে রাখুন।

সুতরাং, যদি ইনপুটটি ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] এর মত হয়, তাহলে আউটপুট হবে

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি নোড গঠন সংজ্ঞায়িত করুন, এটিতে cnt এবং 26টি চাইল্ড নোডের একটি অ্যারে রয়েছে, প্রাথমিকভাবে সবগুলি খালি৷

• একটি ফাংশন freeNode() সংজ্ঞায়িত করুন, এটি মাথা নেবে,

• যদি হেড নাল হয়, তাহলে −

  • ফেরত

• আরম্ভ করার জন্য i :=0, যখন i <26, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন

  • freeNode(মাথার শিশু[i])

• মাথা মুছুন

• একটি ফাংশন সংজ্ঞায়িত করুন insertNode(), এটি নোড, s,

  নেবে

• curr =নোড

• আরম্ভ করার জন্য i :=0, যখন i

  • x :=s[i]

  • যদি নোডের শিশু[x - 'a'] শূন্য না হয়, তাহলে

    • নোডের শিশু [x - 'a'] :=একটি নতুন নোড

  • নোড :=শিশু [x - 'a'] নোডের

  • নোডের cnt 1 দ্বারা বৃদ্ধি করুন

• একটি ফাংশন সংক্ষেপে সংজ্ঞায়িত করুন(), এটি নোড, এস,

  নেবে

• ret :=ফাঁকা স্ট্রিং

• curr =নোড

• আরম্ভ করার জন্য i :=0, যখন i

  • x :=s[i]

  • curr :=শিশু [x - 'a'] curr

  • যদি curr এর cnt 1 এর সমান হয়, তাহলে −

    • rem :=s এর আকার

    • ret :=(যদি rem <=1, তাহলে s, অন্যথায় s-এর সাবস্ট্রিং ইনডেক্স 0 থেকে i concatenate rem-কে s-এর শেষ উপাদান হিসাবে স্ট্রিং কনক্যাটেনেট হিসাবে ব্যবহার করুন

    • লুপ থেকে বেরিয়ে আসুন

• রিটার্ন রিটার্ন

• একটি ফাংশন সংজ্ঞায়িত করুন শব্দ সংক্ষেপণ(), এটি একটি অ্যারে ডিক্ট নেবে,

• n :=dict এর আকার

• n

  আকারের একটি অ্যারে রেট সংজ্ঞায়িত করুন

• একটি ম্যাপ সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • শব্দ :=dict[i]

  • rem :=শব্দের আকার - 2

  • x :=(যদি rem <=1 হয়, তাহলে শব্দ, অন্যথায় শব্দের প্রথম উপাদান concatenate rem concatenate শব্দের শেষ উপাদান)

  • m[x]

    এর শেষে i ঢোকান

  • ret[i] :=x

• প্রতিটি কী-মানের জন্য এটিকে m তে যুক্ত করুন, −

  করুন

  • যদি এর মানের মাপ হয় <=1, তাহলে −

    • (এটি 1 দ্বারা বাড়ান)

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • head :=একটি নতুন নোড

  • আরম্ভ করার জন্য i :=0, যখন i <এর মানের আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

    • idx :=এর মান[i]

    • insertNode(head, dict[idx])

  • আরম্ভ করার জন্য i :=0, যখন i <এর মানের আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

    • idx :=এর মান[i]

    • ret[idx] :=সংক্ষেপে(head, dict[idx])

  • freeNode(head)

  • (এটি 1 দ্বারা বাড়ান)

• রিটার্ন রিটার্ন

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
struct Node{
   int cnt;
   Node* child[26];
   Node(){
      cnt = 0;
      for(int i = 0; i < 26; i++)child[i] = NULL;
   }
};
class Solution {
   public:
   void freeNode(Node* head){
      if (!head)
      return;
      for (int i = 0; i < 26; i++) {
         freeNode(head->child[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;
   }
};
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, ]