Wordの追加と検索-C++でのデータ構造設計

• addWord（word）

• 検索（単語）

search（word）メソッドは、文字a〜zまたは..Aのみを含むリテラル単語または正規表現文字列を検索できます。これは、任意の1文字を表すことができることを意味します。たとえば、「bad」、「dad」、「mad」などの単語を追加すると、search（ "pad"）→false、search（ "bad"）→true、search（ "。ad"）を検索します。 →trueおよびsearch（“ b ..”）→true

これを解決するには、次の手順に従います-

• いくつかのメソッドがあり、最初にinsertNode（）を定義します。これは、ヘッド参照と文字列sを取ります。これは、次のように機能します-

• curr：=ヘッド、n：=sのサイズ

• 0からn–1の範囲のiの場合

  • x：=s [i]

  • currのchild[x]がnullでない場合、currのchild [x]：=new node

  • curr：=currの子[x]

• isEndofcurrをtrueに設定

• addWord（）から、このinsertNode（）メソッドを呼び出します

• check（）と呼ばれる別のメソッドを定義します。これには、curr、string s、およびindexが必要です。最初のインデックスは0です。これは次のように機能します-

• index =sのサイズの場合、isEnd of curr

  を返します。

• set ok：=true

• s [index]がドットの場合、

  • 0から25の範囲のiの場合

    • x：=「a」+iのASCII

    • currのchild[x]AND check（curr、s、index + 1のchild[x]）がtrueの場合、trueを返します。

• それ以外の場合

  • x：=s [index]

  • currのchild[x]AND check（curr、s、index + 1のchild[x]）がtrueの場合、trueを返します。

• falseを返す

• 検索メソッドから、curr：=headを設定し、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