Thêm và Tìm kiếm Word - Thiết kế cấu trúc dữ liệu trong C ++

Giả sử chúng ta phải thiết kế một cấu trúc dữ liệu hỗ trợ hai hoạt động sau -

addWord (từ)
tìm kiếm (từ)

Phương thức search (word) có thể tìm kiếm một từ theo nghĩa đen hoặc một chuỗi biểu thức chính quy chỉ chứa các chữ cái a-z hoặc .. A. có nghĩa là nó có thể đại diện cho bất kỳ một chữ cái nào. Vì vậy, ví dụ:nếu chúng tôi thêm một số từ như "tệ", "cha", "điên", sau đó tìm kiếm tìm kiếm ("pad") → sai, tìm kiếm ("xấu") → đúng, tìm kiếm (". Ad") → true và tìm kiếm (“b ..”) → true

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Có một số phương thức, ban đầu hãy xác định insertNode (), điều này sẽ lấy tham chiếu head và chuỗi s, điều này sẽ hoạt động như sau -
curr:=head, n:=size of s
cho tôi trong phạm vi từ 0 đến n - 1
- x:=s [i]
- nếu con [x] của curr không phải là null, thì con [x] của curr:=nút mới
- curr:=child [x] of curr
đặt isEnd of curr là true
Từ addWord (), gọi phương thức insertNode () này
Định nghĩa một phương thức khác được gọi là check (), phương thức này sẽ nhận curr, string s và index. Ban đầu chỉ mục là 0. Điều này sẽ hoạt động như sau -
nếu index =size of s, thì trả về isEnd of curr
đặt ok:=true
nếu s [index] là dấu chấm thì
- cho tôi trong phạm vi từ 0 đến 25
  - x:=ASCII của ‘a’ + i
  - nếu con [x] của curr AND kiểm tra (con [x] của curr, s, index + 1) là đúng, thì trả về true.
nếu không thì
- x:=s [chỉ số]
- nếu con [x] của curr AND kiểm tra (con [x] của curr, s, index + 1) là đúng, thì trả về true.
trả về false
Từ phương pháp tìm kiếm, đặt curr:=head và return check (curr, word, 0)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra