C++ এ ন্যূনতম অনন্য শব্দ সংক্ষেপণ

ধরুন আমাদের একটি স্ট্রিং আছে যেমন "শব্দ" এবং এতে নিম্নলিখিত সংক্ষিপ্ত রূপ রয়েছে:["শব্দ", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]। আমাদের একটি অভিধানে একটি টার্গেট স্ট্রিং এবং স্ট্রিংগুলির একটি সেটও রয়েছে, আমাদেরকে এই টার্গেট স্ট্রিংটির সংক্ষিপ্ত রূপ খুঁজে বের করতে হবে সম্ভাব্য ক্ষুদ্রতম দৈর্ঘ্যের সাথে যাতে এটি অভিধানে স্ট্রিংগুলির সংক্ষেপণের সাথে বিরোধ না করে। এখানে সংক্ষেপে প্রতিটি সংখ্যা বা অক্ষর দৈর্ঘ্য =1 হিসাবে বিবেচিত হয়। সুতরাং উদাহরণ হিসাবে, "a32bc" সংক্ষেপণটি দৈর্ঘ্য =4।

সুতরাং, যদি ইনপুটটি "আপেল" এর মত হয় এবং অভিধানটি হয় ["ব্লেড"], তাহলে আউটপুট হবে "a4"

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

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

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

• ret :=n

• শুরু করার জন্য b :=3, যখন b

  • যদি (মাস্ক AND b) 0 এর মত হয়, তাহলে −

    • (1 দ্বারা ret কমান)

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

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

  লাগবে

• len :=abbrLen(মাস্ক)

• যদি len>=minLen হয়, তাহলে −

  • ফেরত

• ম্যাচ :=সত্য

• প্রতিটি d-এর জন্য dict, do −

  • যদি (মাস্ক AND d) 0 এর মত হয়, তাহলে −

    • মিল :=মিথ্যা

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

• যদি ম্যাচ অ-শূন্য হয়, তাহলে −

  • minLen :=len

  • মিনাব :=মাস্ক

• অন্যথা -

  • শুরু করার জন্য b :=বিট, যখন b

    • যদি (cand AND b) 0 এর সমান না হয়, তাহলে −

      • dfs(b*2, মুখোশ বা b)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

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

• n :=লক্ষ্যের আকার

• bn :=2^n

• cand :=0

• minLen :=inf

• অভিধানে −

  প্রতিটি s-এর জন্য

  • যদি s এর আকার n এর সমান না হয়, তাহলে −

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

  • শব্দ :=0

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

    • যদি s[i] লক্ষ্য[i] এর সমান না হয়, তাহলে −

      • শব্দ :=শব্দ বা (2^i)

  • ডিক্টের শেষে শব্দ সন্নিবেশ করুন

  • cand :=cand OR word

• dfs(1, 0)

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

  • যদি (minab AND 2^i) 0 এর সমান না হয়, তাহলে −

    • ret :=ret + টার্গেট[i]

    • (i 1 দ্বারা বাড়ান)

  • অন্যথায়

    • j :=i

    • যখন (i

      • (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