C++ में शब्द जोड़ें और खोजें - डेटा संरचना डिज़ाइन

मान लें कि हमें एक डेटा संरचना डिज़ाइन करनी है जो निम्नलिखित दो ऑपरेशन का समर्थन करती है -

• addWord(word)

• search(word)

search(word) मेथड एक शाब्दिक शब्द या केवल अक्षर a-z या . वाला एक रेगुलर एक्सप्रेशन स्ट्रिंग खोज सकता है। एक . का अर्थ है कि यह किसी एक अक्षर को दर्शा सकता है। इसलिए उदाहरण के लिए, यदि हम "bad", "dad", "mad" जैसे कुछ शब्द जोड़ते हैं, तो search("pad") → false, search("bad") → true, search(".ad") → true और search("b..") → true होगा।

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

• कुछ मेथड हैं, प्रारंभ में insertNode() परिभाषित करें, यह हेड रेफरेंस और स्ट्रिंग s लेगा, यह निम्नानुसार काम करेगा -

• curr := head, n := s का आकार

• i को 0 से n - 1 तक रेंज में लिए

  • x := s[i]

  • यदि curr का child[x] नल नहीं है, तो curr का child[x] := नया नोड

  • curr := curr का child[x]

• curr के isEnd को ट्रू सेट करें

• addWord() से, इस insertNode() मेथड को कॉल करें

• check() नामक एक और मेथड परिभाषित करें, यह curr, स्ट्रिंग s, और इंडेक्स लेगा। प्रारंभ में इंडेक्स 0 है। यह निम्नानुसार काम करेगा -

• यदि इंडेक्स = s का आकार, तो curr का isEnd लौटाएं

• ok := ट्रू सेट करें

• यदि s[इंडेक्स] डॉट है, तो

  • i को 0 से 25 तक रेंज में लिए

    • x := 'a' का ASCII + i

    • यदि curr का child[x] और check(curr का child[x], s, इंडेक्स + 1) ट्रू है, तो ट्रू लौटाएं।

• अन्यथा

  • x := s[इंडेक्स]

  • यदि curr का child[x] और check(curr का child[x], s, इंडेक्स + 1) ट्रू है, तो ट्रू लौटाएं।

• फाल्स लौटाएं

• search मेथड से, curr := head सेट करें और check(curr, word, 0) लौटाएं

उदाहरण (C++)

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

#include 
using namespace std;
struct Node{
    bool isEnd;
    map  child;
    Node(){
        isEnd = false;
    }
};
class WordDictionary {
    public:
    Node* head;
    WordDictionary() {
        head = new Node();
    }
    void insertNode(Node* head, string s){
        Node* curr = head;
        int n = s.size();
        for(int i = 0; i < n; i++){
            char x = s[i];
            if(!curr->child[x]){
                curr->child[x] = new Node();
            }
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    void addWord(string word) {
        insertNode(head, word);
    }
    bool check(Node* curr, string s, int idx = 0){
        if(idx == s.size()) return curr->isEnd;
        bool ok = false;
        if(s[idx] == '.'){
            for(int i = 0; i < 26; i++){
                char x = 'a' + i;
                if(curr->child[x] && check(curr->child[x], s, idx + 1)) return true;
            }
        } else {
            char x = s[idx];
            if(curr->child[x] && check(curr->child[x], s, idx + 1)) return true;
        }
        return false;
    }
    bool search(string word) {
        Node* curr = head;
        return check(curr, word);
    }
};
int main(){
    WordDictionary ob;
    ob.addWord("bad");
    ob.addWord("dad");
    ob.addWord("mad");
    cout << (ob.search("pad")) << endl;
    cout << (ob.search("bad")) << endl;
    cout << (ob.search(".ad")) << endl;
    cout << (ob.search("b..")) << endl;
}

इनपुट

WordDictionary आरंभ करें, फिर addWord() मेथड और search मेथड कॉल करें। main() फंक्शन में देखें

आउटपुट

0 1 1 1