C++ में न्यूनतम अद्वितीय शब्द संक्षिप्तिकरण

मान लीजिए कि हमारे पास एक स्ट्रिंग है जैसे "शब्द" और जिसमें निम्नलिखित संक्षिप्त रूप हैं:["शब्द", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]। हमारे पास एक लक्ष्य स्ट्रिंग और एक शब्दकोश में स्ट्रिंग्स का एक सेट भी है, हमें इस लक्ष्य स्ट्रिंग का संक्षिप्त नाम सबसे छोटी संभव लंबाई के साथ खोजना होगा जैसे कि यह शब्दकोश में स्ट्रिंग्स के संक्षेपों के साथ संघर्ष नहीं करता है। यहाँ संक्षेप में प्रत्येक संख्या या अक्षर को लंबाई =1 माना जाता है। उदाहरण के तौर पर, संक्षिप्त नाम "a32bc" लंबाई =4 का है।

इसलिए, यदि इनपुट "सेब" जैसा है, और शब्दकोश ["ब्लेड"] है, तो आउटपुट "a4" होगा

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

• ऐरे डिक्ट को परिभाषित करें

• एक फ़ंक्शन को परिभाषित करें abbrLen(), यह मुखौटा लेगा,

• रिट :=n

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

  • अगर (मुखौटा और बी) 0 के समान है, तो -

    • (रिटर्न 1 से घटाएं)

• वापसी रिट

• एक फ़ंक्शन को परिभाषित करें dfs(), इसमें थोड़ा सा, मास्क लगेगा,

• लेन:=abbrLen(मुखौटा)

• अगर लेन>=minLen, तो −

  • वापसी

• मैच :=सच

• प्रत्येक d के लिए dict, करें -

  • अगर (मास्क और डी) 0 के समान है, तो -

    • मैच :=झूठा

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

• अगर मैच गैर-शून्य है, तो -

  • मिनलेन:=लेन

  • मीनाब:=मुखौटा

• अन्यथा -

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

    • अगर (कैंड और बी) 0 के बराबर नहीं है, तो -

      • dfs(b*2, mask OR b)

• मुख्य विधि से निम्न कार्य करें -

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

• n :=लक्ष्य का आकार

• बीएन:=2^एन

• कैंडी:=0

• मिनलेन :=inf

• शब्दकोश में प्रत्येक s के लिए -

  • यदि s का आकार n के बराबर नहीं है, तो -

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

  • शब्द:=0

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

    • यदि s[i] लक्ष्य के बराबर नहीं है[i], तो -

      • शब्द:=शब्द या (2^i)

  • dict के अंत में शब्द डालें

  • कैंडी:=कैंडी या शब्द

• डीएफएस(1, 0)

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

  • अगर (मिनाब और 2^i) 0 के बराबर नहीं है, तो -

    • रिट :=रिट + टारगेट [i]

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

  • अन्यथा

    • जे:=मैं

    • जबकि (i

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

    • ret :=ret concatenate (i - j)

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int n, cand, bn, minLen, minab;
   vector<int> dict;
   int abbrLen(int mask) {
      int ret = n;
      for (int b = 3; b < bn; b <<= 1) {
         if ((mask & b) == 0)
            ret--;
      }
      return ret;
   }
   void dfs(int bit, int mask) {
      int len = abbrLen(mask);
      if (len >= minLen)
         return;
      bool match = true;
      for (int d : dict) {
         if ((mask & d) == 0) {
            match = false;
         break;
      }
   }
   if (match) {
      minLen = len;
      minab = mask;
   }
   else {
      for (int b = bit; b < bn; b <<= 1) {
         if ((cand & b) != 0)
            dfs(b << 1, mask | b);
         }
      }
   }
   string minAbbreviation(string target, vector<string> &dictionary) {
      string ret = "";
      n = target.size();
      bn = 1 << n;
      cand = 0;
      minLen = INT_MAX;
      for (string &s : dictionary) {
         if (s.size() != n)
            continue;
         int word = 0;
         for (int i = 0; i < s.size(); i++) {
            if (s[i] != target[i])
               word |= (1 << i);
         }
         dict.push_back(word);
         cand |= word;
      }
      dfs(1, 0);
      for (int i = 0; i < n;) {
         if ((minab & (1 << i)) != 0) {
            ret += target[i];
            i++;
         }
         else {
            int j = i;
            while (i < n && (minab & (1 << i)) == 0)
               i++;
            ret += to_string(i - j);
         }
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<string> v = {"blade"};
   cout << (ob.minAbbreviation("apple",v));
}

इनपुट

"apple",{"blade"}

आउटपुट

a4