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

कैरेक्टर स्ट्रीम C++ में

मान लीजिए हम StreamChecker क्लास को निम्नानुसार लागू करना चाहते हैं:

  • StreamChecker(words) - यह कंस्ट्रक्टर है, जो दिए गए शब्दों के साथ डेटा संरचना को इनिशियलाइज़ करता है।

  • query(letter) - यह तब true लौटाता है जब कुछ k >= 1 के लिए, अंतिम k क्वेरी किए गए वर्ण (पुराने से नए क्रम में, इस नए क्वेरी किए गए अक्षर सहित) दी गई सूची में से किसी एक शब्द को स्पेल करते हैं।

उदाहरण के लिए, यदि इनपुट शब्द सूची = ["ce", "g", "lm"] है, तो [a,b,c,e,f,g,h,i,j,k,l,m] के लिए कई बार क्वेरी कॉल करें, तो आउटपुट e, g, m के लिए true होगा, और बाकी के लिए false।

हल करने का दृष्टिकोण

हम एक ट्राई (प्रीफिक्स ट्री) का उपयोग करते हैं जहां शब्दों को उल्टे क्रम में संग्रहीत किया जाता है, और सक्रिय नोड्स की एक प्रतीक्षा सूची बनाए रखते हैं:

  • 26 बच्चों और isEnd फ्लैग के साथ एक नोड संरचना परिभाषित करें

  • सभी शब्दों को उल्टे क्रम में ट्राई में डालें

  • प्रत्येक क्वेरी के लिए, प्रतीक्षा सूची में सभी सक्रिय नोड्स को नए वर्ण के साथ अपडेट करें

  • यदि कोई नोड शब्द के अंत तक पहुंचता है, तो true लौटाएं

  • अगली क्वेरी के लिए प्रतीक्षा सूची अपडेट करें

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    Node* child[26]; 
    bool isEnd; 
    Node(){ 
        isEnd = false; 
        for (int i = 0; i < 26; i++) child[i] = NULL; 
    } 
}; 

class StreamChecker { 
public: 
    Node* head; 
    vector<Node*> waitList; 
    
    void insertNode(Node* head, string& s){ 
        Node* curr = head; 
        for (int i = 0; i < s.size(); i++) { 
            char x = s[i]; 
            if (!curr->child[x - 'a']) { 
                curr->child[x - 'a'] = new Node(); 
            } 
            curr = curr->child[x - 'a']; 
        } 
        curr->isEnd = true; 
    } 
    
    StreamChecker(vector<string>& words){ 
        head = new Node(); 
        for (int i = 0; i < words.size(); i++) { 
            insertNode(head, words[i]); 
        } 
    } 
    
    bool query(char x){ 
        vector<Node*> temp; 
        if (head->child[x - 'a']) { 
            waitList.push_back(head); 
        } 
        bool ret = false; 
        for (int i = 0; i < waitList.size(); i++) { 
            Node* curr = waitList[i]; 
            if (curr->child[x - 'a']) { 
                curr = curr->child[x - 'a']; 
                temp.push_back(curr); 
                ret |= curr->isEnd; 
            } 
        } 
        swap(temp, waitList); 
        return ret; 
    } 
}; 

int main(){ 
    vector<string> v = {"ce","g","lm"}; 
    StreamChecker ob(v); 
    cout << (ob.query('a')) << endl; 
    cout << (ob.query('b')) << endl; 
    cout << (ob.query('c')) << endl; 
    cout << (ob.query('e')) << endl; 
    cout << (ob.query('f')) << endl; 
    cout << (ob.query('g')) << endl; 
    cout << (ob.query('h')) << endl; 
    cout << (ob.query('i')) << endl; 
    cout << (ob.query('j')) << endl; 
    cout << (ob.query('k')) << endl; 
    cout << (ob.query('l')) << endl; 
    cout << (ob.query('m')); 
    return 0;
}

इनपुट

"ce","g","lm", query()

आउटपुट

0 0 0 1 0 1 0 0 0 0 0 1
  1. C++ में सबसे बड़ा BST सबट्री - अधिकतम नोड्स वाला BST खोजें C++ में सबसे बड़ा BST सबट्री - अधिकतम नोड्स वाला BST खोजें

    समस्या विवरण मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उसका सबसे बड़ा सबट्री ढूंढना है जहां सबसे बड़ा का अर्थ है सबसे अधिक नोड्स वाला सबट्री। उदाहरण के लिए, यदि इनपुट इस तरह का ट्री है: तो आउटपुट 3 होगा, क्योंकि इस मामले में सबसे बड़ा BST सबट्री हाइलाइट किया गया है। समाधान दृष्टिकोण पोस्ट-ऑर्ड

  1. C++ स्ट्रीम क्लासेस की संरचना C++ स्ट्रीम क्लासेस की संरचना

    C++ में स्ट्रीम प्रोग्राम थ्रेड और I/O के बीच स्थानांतरित होने वाले वर्णों की स्ट्रीम को संदर्भित करता है। स्ट्रीम क्लासेस C++ में फाइलों और I/O डिवाइस पर इनपुट और आउटपुट ऑपरेशन के लिए उपयोग की जाती हैं। इन क्लासेस में प्रोग्राम के इनपुट और आउटपुट को संभालने के लिए विशिष्ट विशेषताएं होती हैं। iostre

  1. - C++ में ट्राइग्राफ

    ISO-646 कैरेक्टर सेट में C सिंटैक्स के सभी वर्ण नहीं होते, इसलिए कुछ सिस्टम कीबोर्ड और डिस्प्ले के साथ हैं जो कुछ वर्णों को नहीं संभाल सकते। इन वर्णों को 3 वर्णों के अनुक्रम का उपयोग करके बनाया जा सकता है जिसे ट्राइग्राफ कहा जाता है। C में, किसी भी अन्य प्रसंस्करण से पहले, निम्नलिखित तीन-वर्ण अनुक्