सी++ में वर्ड को स्पेल करने के लिए स्टिकर्स

मान लीजिए कि हमारे पास N विभिन्न प्रकार के स्टिकर हैं। प्रत्येक प्रकार के स्टिकर में एक लोअरकेस अंग्रेजी शब्द होता है। हम स्टिकर के हमारे संग्रह से अलग-अलग अक्षरों को काटकर और उन्हें पुनर्व्यवस्थित करके दिए गए लक्ष्य स्ट्रिंग को स्पष्ट करना चाहते हैं। यदि आवश्यक हो तो हम प्रत्येक स्टिकर का एक से अधिक बार उपयोग कर सकते हैं, और हमारे पास प्रत्येक स्टिकर की अनंत मात्रा है।

हमें स्टिकर्स की न्यूनतम संख्या ज्ञात करनी है जो हमें लक्ष्य को स्पष्ट करने के लिए चाहिए? यदि कार्य असंभव है, तो -1 लौटें।

तो अगर इनपुट ["कुत्ता", "वाक्य", "एंटीना"] जैसा है, और लक्ष्य "नृत्य" है, तो उत्तर 3

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

• n :=लक्ष्य का आकार
• N :=1 को बाईं ओर n बार शिफ्ट करें
• आकार एन के एक सरणी डीपी को परिभाषित करें इसे inf के साथ प्रारंभ करें
• dp[0] :=0
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• यदि dp[i], inf के समान है, तो −
  • निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
• इनिशियलाइज़ j :=0 के लिए, जब j <स्टिकर का आकार, अपडेट करें (1 से j बढ़ाएँ), −
  करें
  • s :=स्टिकर[j]
  • x :=मैं
  • इनिशियलाइज़ 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