मान लीजिए हमारे पास N विभिन्न प्रकार के स्टिकर्स हैं। प्रत्येक प्रकार के स्टिकर पर एक लोअरकेस अंग्रेजी शब्द है। हम दिए गए लक्ष्य स्ट्रिंग को अपने स्टिकर्स के संग्रह से अलग-अलग अक्षरों को काटकर और उन्हें पुनर्व्यवस्थित करके लिखना चाहेंगे। हम आवश्यकता पड़ने पर प्रत्येक स्टिकर का एक से अधिक बार उपयोग कर सकते हैं, और हमारे पास प्रत्येक स्टिकर की अनंत मात्रा है।
हमें लक्ष्य को लिखने के लिए आवश्यक न्यूनतम स्टिकर्स की संख्या ज्ञात करनी है? यदि कार्य असंभव है, तो -1 वापस करें।
तो यदि इनपुट ["dog", "sentence", "antenna"] जैसा है, और लक्ष्य "dance" है, तो उत्तर 3 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- n := target का आकार
- N := 1 को बाएं n बार शिफ्ट करें
- आकार N का एक ऐरे dp परिभाषित करें जिसे inf से आरंभ करें
- dp[0] := 0
- i := 0 से प्रारंभ करें, जब i < N, i बढ़ाते हुए, करें -
- यदि dp[i], inf के समान है, तो -
- अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
- j := 0 से प्रारंभ करें, जब j < stickers का आकार, j बढ़ाते हुए, करें -
- s := stickers[j]
- x := i
- k := 0 से प्रारंभ करें, जब k < s का आकार, k बढ़ाते हुए, करें -
- z := s[k]
- l := 0 से प्रारंभ करें, जब l < target का आकार, l बढ़ाते हुए, करें -
- यदि target[l], z के समान है और (x को दाएं l बिट शिफ्ट करना) AND 1) 0 के समान है, तो -
- x := x OR (1 को बाएं l बिट शिफ्ट करें)
- लूप से बाहर निकलें
- यदि target[l], z के समान है और (x को दाएं l बिट शिफ्ट करना) AND 1) 0 के समान है, तो -
- dp[x] := dp[x] और dp[i] + 1 का न्यूनतम
- यदि dp[i], inf के समान है, तो -
- यदि dp[N - 1], inf है तो -1 के साथ सेट करें अन्यथा dp[N - 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