सी ++ में शब्द संक्षिप्तिकरण

मान लीजिए कि हमारे पास n अद्वितीय स्ट्रिंग्स की एक सरणी है, हमें नीचे दिए गए नियमों का पालन करते हुए प्रत्येक शब्द के लिए न्यूनतम संभव संक्षिप्तीकरण उत्पन्न करना होगा।

• पहले वर्ण से प्रारंभ करें और फिर संक्षिप्त वर्णों की संख्या, उसके बाद अंतिम वर्ण।

• यदि हमें कोई विरोध मिलता है और वह है एक से अधिक शब्द समान संक्षिप्त नाम साझा करते हैं, तो केवल पहले वर्ण के बजाय एक लंबे उपसर्ग का उपयोग किया जा सकता है जब तक कि मानचित्र को शब्द से संक्षिप्त नाम तक अद्वितीय नहीं बनाया जाता है।

• जब संक्षिप्त नाम से शब्द छोटा न हो जाए, तो उसे मूल के रूप में ही रखें।

इसलिए, यदि इनपुट ["लाइक", "ईश्वर", "आंतरिक", "मैं", "इंटरनेट", "अंतराल", "इंटेंस", "फेस", "घुसपैठ"] जैसा है, तो आउटपुट होगा

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक नोड संरचना को परिभाषित करें, इसमें cnt और 26 चाइल्ड नोड्स की एक सरणी है, शुरू में सभी खाली हैं।

• एक फ़ंक्शन को परिभाषित करें freeNode(), यह सिर लेगा,

• यदि सिर शून्य है, तो -

  • वापसी

• प्रारंभ करने के लिए मैं:=0, जब मैं <26, अद्यतन (मैं 1 से बढ़ाएँ), करते हैं

  • फ्रीनोड (सिर का बच्चा [i])

• सिर हटाएं

• एक फ़ंक्शन इन्सर्टनोड () को परिभाषित करें, यह नोड लेगा, s,

• curr =नोड

• इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -

  • एक्स:=एस [i]

  • यदि नोड का बच्चा [x - 'a'] रिक्त नहीं है, तो

    • बच्चे [x - 'ए'] नोड का:=एक नया नोड

  • नोड:=बच्चे [x - 'ए'] नोड के

  • नोड के cnt को 1 से बढ़ाएँ

• एक फ़ंक्शन को संक्षिप्त करें () परिभाषित करें, यह नोड लेगा, s,

• रिट:=खाली स्ट्रिंग

• curr =नोड

• इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -

  • एक्स:=एस [i]

  • curr :=बच्चा [x - 'a'] curr का

  • अगर cnt curr 1 के समान है, तो -

    • रेम :=आकार का

    • ret :=(यदि रेम <=1, तो s, अन्यथा s की अनुक्रमणिका 0 से i को प्रतिस्थापित करते हुए, s के अंतिम तत्व को स्ट्रिंग के रूप में संयोजित करना

    • लूप से बाहर आएं

• वापसी रिट

• एक फ़ंक्शन को परिभाषित करें शब्दसंक्षिप्तता(), यह एक सरणी निर्देश लेगा,

• n :=निर्देश का आकार

• आकार n के सरणी रिट को परिभाषित करें

• एक मैप परिभाषित करें

• इनिशियलाइज़ i:=0 के लिए, जब i

  • शब्द :=dict[i]

  • रेम :=शब्द का आकार - 2

  • x :=(यदि रेम <=1 है, तो शब्द, अन्यथा शब्द का पहला तत्व कॉन्सटेनेट रेम कॉन्टेनेट शब्द का अंतिम तत्व)

  • m[x]

    . के अंत में i डालें

  • रिट[i] :=x

• प्रत्येक की-वैल्यू पेयर के लिए इसे m में जोड़ें -

  • यदि इसके मान का आकार <=1 है, तो -

    • (इसे 1 से बढ़ाएं)

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • सिर :=एक नया नोड

  • इनिशियलाइज़ करने के लिए:=0, जब मैं <इसके मूल्य का आकार, अद्यतन (i से 1 बढ़ाएँ), करें -

    • idx :=value[i] इसका

    • insertNode(सिर, तानाशाही [idx])

  • इनिशियलाइज़ करने के लिए:=0, जब मैं <इसके मूल्य का आकार, अद्यतन (i से 1 बढ़ाएँ), करें -

    • idx :=value[i] इसका

    • ret[idx] :=abbreviate(head, dict[idx])

  • फ्रीनोड(सिर)

  • (इसे 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, ]