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

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

• ऐडवर्ड (शब्द)

• खोज (शब्द)

खोज (शब्द) विधि एक शाब्दिक शब्द या एक नियमित अभिव्यक्ति स्ट्रिंग खोज सकती है जिसमें केवल अक्षर a-z या .. A हो। इसका मतलब है कि यह किसी एक अक्षर का प्रतिनिधित्व कर सकता है। तो उदाहरण के लिए, यदि हम "बुरा", "पिताजी", "पागल" जैसे कुछ शब्द जोड़ते हैं, तो खोज ("पैड") → झूठा, खोज ("खराब") → सत्य, खोज (".ad") खोजें। → सत्य और खोज ("बी ..") → सत्य

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

• कुछ विधियाँ हैं, शुरू में इन्सर्टनोड () को परिभाषित करें, यह हेड रेफरेंस और स्ट्रिंग s लेगा, यह निम्नानुसार काम करेगा -

• वक्र:=सिर, n:=s का आकार

• मेरे लिए 0 से n - 1 की सीमा में

  • एक्स:=एस [i]

  • अगर बच्चे [x] का curr शून्य नहीं है, तो बच्चे [x] का curr :=new node

  • curr :=बच्चे [x] करी के

• isEnd of curr को सच के रूप में सेट करें

• AddWord() से, इस insertNode() विधि को कॉल करें

• चेक () नामक एक अन्य विधि को परिभाषित करें, यह curr, string s और index लेगा। प्रारंभ में सूचकांक 0 है। यह निम्नानुसार काम करेगा -

• यदि अनुक्रमणिका =s का आकार, तो वापसी isEnd of curr

• ठीक सेट करें:=सच

• अगर s[index] डॉट है, तो

  • मेरे लिए 0 से 25 की सीमा में

    • x :='a' + i

      . का ASCII

    • अगर बच्चे [x] का कर्व और चेक (बच्चा [x] का curr, s, index + 1) सही है, तो सही लौटें।

• अन्यथा

  • एक्स:=एस [सूचकांक]

  • अगर बच्चे [x] का कर्व और चेक (बच्चा [x] का curr, s, index + 1) सही है, तो सही लौटें।

• झूठी वापसी

• खोज विधि से, curr :=head और return check(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

आउटपुट

0
1
1
1