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

C++ में शब्द संक्षिप्तीकरण (Word Abbreviation)


मान लीजिए हमारे पास n अद्वितीय स्ट्रिंग्स की एक सरणी है, हमें नीचे दिए गए नियमों का पालन करते हुए हर शब्द के लिए न्यूनतम संभव संक्षिप्तीकरण उत्पन्न करना है।

  • पहले वर्ण से शुरू करें और फिर संक्षिप्त किए गए वर्णों की संख्या, जिसके बाद अंतिम वर्ण आता है।
  • यदि हमें कोई संघर्ष मिलता है और एक से अधिक शब्द समान संक्षिप्तीकरण साझा करते हैं, तो केवल पहले वर्ण के बजाय एक लंबा उपसर्ग तब तक उपयोग किया जा सकता है जब तक कि शब्द से संक्षिप्तीकरण का मानचित्र अद्वितीय न हो जाए।
  • जब संक्षिप्तीकरण शब्द को छोटा नहीं बनाता है, तो इसे मूल रूप में ही रखें।

इसलिए, यदि इनपुट ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"] जैसा है, तो आउटपुट होगा:

["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • एक नोड संरचना परिभाषित करें, जिसमें cnt और 26 चाइल्ड नोड्स की एक सरणी हो, प्रारंभ में सभी खाली हों।
  • एक फ़ंक्शन freeNode() परिभाषित करें, जो head लेगा,
    • यदि head null है, तो वापस लौटें
    • i := 0 से 25 तक लूप चलाएं:
      • freeNode(head के child[i])
    • head को डिलीट करें
  • एक फ़ंक्शन insertNode() परिभाषित करें, जो node, s लेगा,
    • curr = node
    • i := 0 से s का आकार - 1 तक लूप चलाएं:
      • x := s[i]
      • यदि node के child[x - 'a'] null नहीं है, तो:
        • node के child[x - 'a'] := एक नया नोड
      • node := node के child[x - 'a']
      • node के cnt को 1 से बढ़ाएं
  • एक फ़ंक्शन abbreviate() परिभाषित करें, जो node, s लेगा,
    • ret := खाली स्ट्रिंग
    • curr = node
    • i := 0 से s का आकार - 1 तक लूप चलाएं:
      • x := s[i]
      • curr := curr के child[x - 'a']
      • यदि curr का cnt == 1 है, तो:
        • rem := s का आकार - (i + 2)
        • ret := (यदि rem <= 1, तो s, अन्यथा s का सबस्ट्रिंग इंडेक्स 0 से i तक + rem को स्ट्रिंग में + s का अंतिम तत्व)
        • लूप से बाहर निकलें
    • ret वापस करें
  • एक फ़ंक्शन wordsAbbreviation() परिभाषित करें, जो एक सरणी dict लेगा,
    • n := dict का आकार
    • आकार n की एक सरणी ret परिभाषित करें
    • एक मैप m परिभाषित करें
    • i := 0 से n-1 तक लूप चलाएं:
      • word := dict[i]
      • rem := word का आकार - 2
      • x := (यदि rem <= 1, तो word, अन्यथा word का पहला तत्व + rem + word का अंतिम तत्व)
      • m[x] के अंत में i डालें
      • ret[i] := x
    • मैप m में प्रत्येक कुंजी-मान जोड़ी it के लिए:
      • यदि it के मान का आकार <= 1 है, तो:
        • it को बढ़ाएं
        • अगले पुनरावृत्ति पर जाएं
      • head := एक नया नोड
      • i := 0 से it के मान का आकार - 1 तक लूप चलाएं:
        • idx := it के मान[i]
        • insertNode(head, dict[idx])
      • i := 0 से it के मान का आकार - 1 तक लूप चलाएं:
        • idx := it के मान[i]
        • ret[idx] := abbreviate(head, dict[idx])
      • freeNode(head)
      • it को बढ़ाएं
    • ret वापस करें

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

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
void print_vector(vector<auto> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 
struct Node{ 
    int cnt; 
    Node* child[26]; 
    Node(){ 
        cnt = 0; 
        for(int i = 0; i < 26; i++)child[i] = NULL; 
    } 
}; 
class Solution { 
public: 
    void freeNode(Node* head){ 
        if (!head) 
            return; 
        for (int i = 0; i < 26; i++) { 
            freeNode(head->child[i]); 
        } 
        delete head; 
    } 
    void insertNode(Node* node, string s){ 
        Node* curr = node; 
        for (int i = 0; i < s.size(); i++) { 
            char x = s[i]; 
            if (!node->child[x - 'a']) { 
                node->child[x - 'a'] = new Node(); 
            } 
            node = node->child[x - 'a']; 
            node->cnt++; 
        } 
    } 
    string abbreviate(Node* node, string s){ 
        string ret = ""; 
        Node* curr = node; 
        for (int i = 0; i < s.size(); i++) { 
            char x = s[i]; 
            curr = curr->child[x - 'a']; 
            if (curr->cnt == 1) { 
                int rem = s.size() - (i + 2); 
                ret = rem <= 1 ? s : s.substr(0, i + 1) + to_string(rem) + s.back(); 
                break; 
            } 
        } 
        return ret; 
    } 
    vector<string> wordsAbbreviation(vector<string>& dict) { 
        int n = dict.size(); 
        vector<string> ret(n); 
        map<string, vector<int> > m; 
        for (int i = 0; i < n; i++) { 
            string word = dict[i]; 
            int rem = word.size() - 2; 
            string x = rem <= 1 ? word : word.front() + to_string(rem) + word.back(); 
            m[x].push_back(i); 
            ret[i] = x; 
        } 
        Node* head; 
        map<string, vector<int> >::iterator it = m.begin(); 
        while (it != m.end()) { 
            if (it->second.size() <= 1) { 
                it++; 
                continue; 
            } 
            head = new Node(); 
            for (int i = 0; i < it->second.size(); i++) { 
                int idx = it->second[i]; 
                insertNode(head, dict[idx]); 
            } 
            for (int i = 0; i < it->second.size(); i++) { 
                int idx = it->second[i]; 
                ret[idx] = abbreviate(head, dict[idx]); 
            } 
            freeNode(head); 
            it++; 
        } 
        return ret; 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<string> v = 
    {"like","god","internal","me","internet","interval","intension","face","intrusion"}; 
    print_vector(ob.wordsAbbreviation(v)); 
}

इनपुट

{"like","god","internal","me","internet","interval","intension","face","intrusion"}

आउटपुट

[l2e, god, internal, me, i6t, interval, inte4n, f2e, intr4n, ]
  1. C++ में BST में Inorder Successor (द्वितीय संस्करण) C++ में BST में Inorder Successor (द्वितीय संस्करण)

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री में एक नोड है, हमें उस नोड का इन-ऑर्डर सक्सेसर BST में ढूंढना है। यदि कोई इन-ऑर्डर सक्सेसर नहीं है, तो null लौटाएँ। जैसा कि हम जानते हैं कि एक नोड का सक्सेसर वह नोड है जिसका कुंजी मान नोड के मान से सबसे छोटा बड़ा होता है। हमें नोड तक सीधी पहुंच होगी लेकिन ट्र

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

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

  1. C++ में BST से नोड हटाना C++ में BST से नोड हटाना

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है। हमें एक कुंजी k दी जाती है, जिसे BST से हटाकर अपडेटेड BST लौटाना है। उदाहरण: ट्री [5,3,6,2,4,null,7] से कुंजी 3 हटाने पर ट्री [5,4,6,2,null,null,7] बनता है। BST डिलीशन एल्गोरिदम deleteRoot(root) हेल्पर: रूट नोड को हटाता है। यदि राइट सबट्री नहीं