Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में शब्द लिखने के लिए स्टिकर्स (Stickers to Spell Word)


मान लीजिए हमारे पास 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 बिट शिफ्ट करें)
            • लूप से बाहर निकलें
      • dp[x] := dp[x] और dp[i] + 1 का न्यूनतम
  • यदि 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

  1. C++ में BK ट्री परिचय C++ में BK ट्री परिचय

    BK ट्री या बर्कहार्ड ट्री (Burkhard tree) एक प्रकार की डेटा संरचना है जिसका उपयोग आमतौर पर लेवेंश्टाइन दूरी (Levenshtein distance) के आधार पर स्पेल चेक करने के लिए किया जाता है। इसका उपयोग स्ट्रिंग मिलान के लिए ऑटोकरेक्ट फीचर बनाने के लिए भी किया जाता है। मान लें कि हमारे पास एक डिक्शनरी में कुछ शब

  1. - C++ प्रोग्राम फाइल को शब्द दर शब्द पढ़ने के लिए

    इस अनुभाग में हम देखेंगे कि C++ का उपयोग करके फाइल की सामग्री को शब्द दर शब्द कैसे पढ़ा जाए। कार्य बहुत सरल है। हमें फाइल इनपुट स्ट्रीम का उपयोग करके फाइल की सामग्री पढ़नी होगी। फाइल स्ट्रीम फाइल नाम का उपयोग करके फाइल खोलेगा, फिर FileStream का उपयोग करके प्रत्येक शब्द लोड करेगा और इसे word नामक वे

  1. Word में स्पेल चेक काम न करने की समस्या का समाधान Word में स्पेल चेक काम न करने की समस्या का समाधान

    Microsoft Word Microsoft द्वारा विकसित एक वर्ड प्रोसेसर है। यह दशकों से मौजूद है और दुनिया भर में सबसे अधिक उपयोग किया जाने वाला ऑफिस एप्लिकेशन है। इसे Microsoft से ही समय-समय पर अपडेट प्राप्त होते हैं जो विभिन्न मुद्दों को लक्षित करते हैं और विभिन्न सुविधाओं में सुधार करते हैं। Microsoft Word का उप