ওয়ার্ড অ্যাড অ্যান্ড সার্চ - 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 := size of s

• for i in range 0 to n – 1

  • x := s[i]

  • if child[x] of curr is not null, then child[x] of curr := new node

  • curr := child[x] of curr

• curr-এর isEnd কে true সেট করুন

• addWord() থেকে এই insertNode() মেথড কল করুন

• আরেকটি মেথড ডিফাইন করুন যেটি check() নামে, এটি curr, স্ট্রিং s, এবং ইনডেক্স নেবে। প্রাথমিকভাবে ইনডেক্স 0। এটি নিচের মতো কাজ করবে −

• যদি index = size of s, তবে curr-এর isEnd রিটার্ন করুন

• ok := true সেট করুন

• যদি s[index] ডট হয়, তবে

  • for i in range 0 to 25

    • x := ASCII of 'a' + i

    • যদি child[x] of curr AND check(child[x] of curr, s, index + 1) true হয়, তবে true রিটার্ন করুন।

• অন্যথায়

  • x := s[index]

  • যদি child[x] of curr AND check(child[x] of curr, s, index + 1) true হয়, তবে true রিটার্ন করুন।

• false রিটার্ন করুন

• search মেথড থেকে, curr := head সেট করুন এবং return 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