เพิ่มและค้นหา Word - การออกแบบโครงสร้างข้อมูลใน C++

สมมติว่าเราต้องออกแบบโครงสร้างข้อมูลที่รองรับการทำงานสองอย่างต่อไปนี้ -

• addWord(คำ)

• ค้นหา(คำ)

วิธีค้นหา (คำ) สามารถค้นหาคำตามตัวอักษรหรือสตริงนิพจน์ทั่วไปที่มีเฉพาะตัวอักษร a-z หรือ .. A หมายความว่ามันสามารถเป็นตัวแทนของตัวอักษรใดก็ได้ ตัวอย่างเช่น หากเราเพิ่มคำบางคำ เช่น "ไม่ดี", "พ่อ", "บ้า" ให้ค้นหาการค้นหา ("แผ่น") → เท็จ ค้นหา ("ไม่ดี") → จริง ค้นหา (".ad") → จริงและค้นหา (“b..”) → จริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• มีวิธีการบางอย่างในขั้นต้นกำหนด insertNode() สิ่งนี้จะใช้การอ้างอิงส่วนหัวและสตริง s สิ่งนี้จะทำงานดังนี้ -

• curr :=head, n :=size of s

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • x :=s[i]

  • ถ้า child[x] ของ curr ไม่เป็นค่าว่าง ดังนั้น child[x] ของ curr :=new node

  • curr :=child[x] ของสกุลเงิน

• กำหนด isEnd of curr ให้เป็นจริง

• จาก addWord() ให้เรียกเมธอด insertNode() นี้

• กำหนดวิธีการอื่นที่เรียกว่า check() ซึ่งจะใช้ curr, string s และ index ดัชนีเริ่มต้นคือ 0 ซึ่งจะทำงานดังนี้ -

• ถ้า index =ขนาดของ s ให้คืนค่า isEnd of curr

• set ok :=true

• ถ้า s[index] เป็นจุด แล้ว

  • สำหรับผมอยู่ในช่วง 0 ถึง 25

    • x :=ASCII ของ 'a' + i

    • ถ้า child[x] ของ curr และ check(child[x] ของ curr, s, index + 1) เป็นจริง ให้คืนค่า true

• อย่างอื่น

  • x :=s[ดัชนี]

  • ถ้า child[x] ของ curr และ check(child[x] ของ curr, s, index + 1) เป็นจริง ให้คืนค่า true

• คืนค่าเท็จ

• จากวิธีค้นหา ตั้งค่า 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