C++ এ শব্দ বানান করার জন্য স্টিকার

ধরুন আমাদের এন বিভিন্ন ধরনের স্টিকার আছে। প্রতিটি ধরনের স্টিকারে ছোট হাতের ইংরেজি শব্দ থাকে। আমরা আমাদের স্টিকারের সংগ্রহ থেকে পৃথক অক্ষর কেটে এবং তাদের পুনর্বিন্যাস করে প্রদত্ত লক্ষ্য স্ট্রিংটি বানান করতে চাই। প্রয়োজনে আমরা প্রতিটি স্টিকার একাধিকবার ব্যবহার করতে পারি এবং আমাদের কাছে প্রতিটি স্টিকার অসীম পরিমাণে রয়েছে।

আমাদের ন্যূনতম সংখ্যক স্টিকার খুঁজে বের করতে হবে যা আমাদের লক্ষ্য বানান করতে হবে? যদি কাজটি অসম্ভব হয় তবে -1 ফেরত দিন।

সুতরাং ইনপুট যদি হয় [“কুকুর”, “বাক্য”, “অ্যান্টেনা”], এবং লক্ষ্য হয় “নৃত্য”, তাহলে উত্তর হবে 3

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

• n :=লক্ষ্যের আকার
• N :=1 বাম দিকে n বার শিফট করুন
• এন সাইজের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন এটি inf দিয়ে শুরু করুন
• dp[0] :=0
• আরম্ভ করার জন্য i :=0, যখন i করুন
• যদি dp[i] inf এর মত হয়, তাহলে −
  • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
• আরম্ভ করার জন্য j :=0, যখন j <স্টিকারের আকার, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
  • s :=স্টিকার[j]
  • x :=i
  • আরম্ভ করার জন্য k :=0, যখন k করুন
  • z :=s[k]
  • আরম্ভ করার জন্য l :=0, যখন l <লক্ষ্যের আকার, আপডেট করুন (l 1 দ্বারা বৃদ্ধি করুন), করুন −
    • যদি টার্গেট[l] z এর মত হয় এবং (ডান স্থানান্তর করা x, l বিট) এবং 1) 0 এর মত হয়, তাহলে −
      • x :=x OR (1 বাম l বিটে স্থানান্তর করুন)
      • লুপ থেকে বেরিয়ে আসুন
• dp[x] :=ন্যূনতম dp[x] এবং dp[i] + 1

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minStickers(vector<string>& stickers, string target) {
      int n = target.size();
      int N = 1 << n;
      vector <int> dp(N, INT_MAX);
      dp[0] = 0;
      for(int i = 0; i < N; i++){
         if(dp[i] == INT_MAX) continue;
         for(int j = 0; j < stickers.size(); j++){
            string s = stickers[j];
            int x = i;
            for(int k = 0; k < s.size(); k++){
               char z = s[k];
               for(int l = 0; l < target.size(); l++){
                  if(target[l] == z && ((x >> l) & 1) == 0){
                     x |= (1 << l);
                     break;
                  }
               }
            }
            dp[x] = min(dp[x], dp[i] + 1);
         }
      }
      return dp[N - 1] == INT_MAX? -1 : dp[N - 1];
   }
};
main(){
   Solution ob;
   vector<string> v = {"dog", "sentence","antenna"};
   cout << (ob.minStickers(v, "dance"));
}

["dog", "sentence","antenna"]
"dance"

3