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

न्यूनतम अद्वितीय शब्द संक्षिप्तीकरण - C++


मान लीजिए हमारे पास "word" जैसी एक स्ट्रिंग है जिसमें निम्नलिखित संक्षिप्तीकरण हैं: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]। हमारे पास एक लक्ष्य स्ट्रिंग और एक डिक्शनरी में स्ट्रिंग्स का सेट भी है, हमें इस लक्ष्य स्ट्रिंग का एक संक्षिप्तीकरण ढूंढना है जिसमें सबसे छोटी संभव लंबाई हो जैसे कि यह डिक्शनरी में स्ट्रिंग्स के संक्षिप्तीकरणों के साथ संघर्ष न करे। यहां संक्षिप्तीकरण में प्रत्येक संख्या या अक्षर को लंबाई = 1 माना जाता है। तो उदाहरण के लिए, संक्षिप्तीकरण "a32bc" की लंबाई = 4 है।

तो, यदि इनपुट "apple" है, और डिक्शनरी ["blade"] है, तो आउटपुट "a4" होगा

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

  • एक ऐरे dict परिभाषित करें

  • abbrLen() नामक एक फ़ंक्शन परिभाषित करें, जो mask लेगा,

  • ret := n

  • b := 3 से आरंभ करें, जब b < bn, अद्यतन करें b <<= 1, करें −

    • यदि (mask AND b) 0 के समान है, तो −

      • (ret को 1 से घटाएं)

  • ret लौटाएं

  • dfs() नामक एक फ़ंक्शन परिभाषित करें, जो bit, mask लेगा,

  • len := abbrLen(mask)

  • यदि len >= minLen, तो −

    • लौटें

  • match := true

  • dict में प्रत्येक d के लिए, करें −

    • यदि (mask AND d) 0 के समान है, तो −

      • match := false

      • लूप से बाहर आएं

  • यदि match शून्येतर है, तो −

    • minLen := len

    • minab := mask

  • अन्यथा −

    • b := bit से आरंभ करें, जब b < bn, अद्यतन करें b := b*2, करें −

      • यदि (cand AND b) 0 के बराबर नहीं है, तो −

        • dfs(b*2, mask OR b)

  • मुख्य विधि से निम्नलिखित करें −

  • ret := खाली स्ट्रिंग

  • n := target का आकार

  • bn := 2^n

  • cand := 0

  • minLen := inf

  • डिक्शनरी में प्रत्येक s के लिए −

    • यदि s का आकार n के बराबर नहीं है, तो −

      • निम्नलिखित भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं

    • word := 0

    • i := 0 से आरंभ करें, जब i, s के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

      • यदि s[i], target[i] के बराबर नहीं है, तो −

        • word := word OR (2^i)

    • word को dict के अंत में डालें

    • cand := cand OR word

  • dfs(1, 0)

  • i := 0 से आरंभ करें, जब i < n, करें −

    • यदि (minab AND 2^i) 0 के बराबर नहीं है, तो −

      • ret := ret + target[i]

      • (i को 1 से बढ़ाएं)

    • अन्यथा

      • j := i

      • जब तक (i < n और (minab AND 2^i) 0 के समान है), करें −

        • (i को 1 से बढ़ाएं)

      • ret := ret को (i - j) के साथ जोड़ें

  • ret लौटाएं

उदाहरण  

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

#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

  1. C++ में न्यूनतम नाइट मूव्स C++ में न्यूनतम नाइट मूव्स

    मान लीजिए हमारे पास एक अनंत शतरंज बोर्ड है जिसके कोऑर्डिनेट्स -इनफिनिटी से +इनफिनिटी तक हैं, और हमारे पास [0, 0] स्क्वायर पर एक नाइट है। नाइट के 8 संभावित मूव्स होते हैं, जैसा कि नीचे दिखाया गया है। प्रत्येक मूव कार्डिनल डायरेक्शन में दो स्क्वायर, फिर ऑर्थोगोनल डायरेक्शन में एक स्क्वायर होता है। ह

  1. - C++ में ट्राइबोनैकी वर्ड

    ट्राइबोनैकी वर्ड डिजिट्स का एक क्रम है। यह फिबोनैकी वर्ड्स के समान है। ट्राइबोनैकी वर्ड तीन पिछली स्ट्रिंग्स के बार-बार कन्केटनेशन द्वारा बनाया जाता हैT(n) = T(n - 1) + T(n - 2) + T(n - 3)शुरू करने के लिए पहली कुछ स्ट्रिंग्स हैं {1, 12, 1213} तो अगली होगी 1213 + 12 + 1 = 1213121एल्गोरिदमtribonacci_w

  1. - C++ प्रोग्राम: फाइल में अद्वितीय शब्दों को प्रिंट करना

    एक फाइल एक मेमोरी लोकेशन है जो वर्ड स्ट्रीम को संग्रहीत करती है। एक फाइल में विभिन्न शब्द होते हैं। इस प्रोग्राम में, हम फाइल से सभी अद्वितीय शब्दों को ढूंढेंगे और उन्हें प्रिंट करेंगे। एक अद्वितीय शब्द का अर्थ है फाइल में उस शब्द की घटनाओं की संख्या एक है। उदाहरण के लिए, Tutorials point is best for