শব্দ যোগ করুন এবং অনুসন্ধান করুন - C++ এ ডেটা স্ট্রাকচার ডিজাইন

ধরুন আমাদের একটি ডেটা স্ট্রাকচার ডিজাইন করতে হবে যা নিম্নলিখিত দুটি ক্রিয়াকলাপকে সমর্থন করে −

addWord(শব্দ)
অনুসন্ধান(শব্দ)

অনুসন্ধান(শব্দ) পদ্ধতিটি একটি আক্ষরিক শব্দ বা একটি রেগুলার এক্সপ্রেশন স্ট্রিং অনুসন্ধান করতে পারে যেখানে শুধুমাত্র a-z বা .. A অক্ষর রয়েছে। মানে এটি যেকোনো একটি অক্ষর প্রতিনিধিত্ব করতে পারে। সুতরাং উদাহরণস্বরূপ, যদি আমরা "খারাপ", "বাবা", "পাগল" এর মতো কিছু শব্দ যোগ করি, তাহলে অনুসন্ধান ("প্যাড") → মিথ্যা, অনুসন্ধান ("খারাপ") → সত্য, অনুসন্ধান (". বিজ্ঞাপন") অনুসন্ধান করুন। → সত্য এবং অনুসন্ধান (“বি..”) → সত্য

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

কিছু পদ্ধতি আছে, প্রাথমিকভাবে insertNode() সংজ্ঞায়িত করুন, এটি হেড রেফারেন্স এবং স্ট্রিং s নেবে, এটি নিম্নরূপ কাজ করবে -
curr :=head, n :=s
এর আকার
0 থেকে n – 1
রেঞ্জের i জন্য
- x :=s[i]
- যদি curr এর চাইল্ড[x] শূন্য না হয়, তাহলে curr এর চাইল্ড[x] :=নতুন নোড
- curr :=curr এর সন্তান [x]
curr এর শেষকে সত্য হিসাবে সেট করুন
addWord() থেকে, এই insertNode() পদ্ধতিতে কল করুন
চেক() নামে আরেকটি পদ্ধতি সংজ্ঞায়িত করুন, এটি curr, স্ট্রিং s এবং সূচক নেবে। প্রাথমিকভাবে সূচকটি 0। এটি নিম্নরূপ কাজ করবে -
যদি সূচী =s এর আকার, তাহলে curr এর শেষ হয়
ঠিক আছে সেট করুন :=সত্য
যদি s[সূচী] বিন্দু হয়, তাহলে
- আমি 0 থেকে 25 রেঞ্জের জন্য
  - x :='a' + i
    এর ASCII
  - যদি curr-এর চাইল্ড[x] এবং চেক(child[x] of curr, s, index + 1) সত্য হয়, তাহলে true ফেরত দিন।
অন্যথায়
- x :=s[সূচী]
- যদি curr-এর চাইল্ড[x] এবং চেক(child[x] of curr, s, index + 1) সত্য হয়, তাহলে true ফেরত দিন।
মিথ্যা ফেরত দিন
অনুসন্ধান পদ্ধতি থেকে, curr :=হেড এবং রিটার্ন চেক (curr, word, 0)
সেট করুন

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#include <bits/stdc++.h>
using namespace std;
struct Node{
   bool isEnd;
   map <char, Node*> 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);
   }
};
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;
}

ইনপুট

Initialize the WordDictionary, then call the addWord() methods ans search methods. 
See in the main() function

আউটপুট