단어 추가 및 검색 - C++의 데이터 구조 설계

다음 두 가지 작업을 지원하는 데이터 구조를 설계해야 한다고 가정해 보겠습니다.

addWord(단어)
검색(단어)

search(word) 메서드는 문자 a-z 또는 .. A 만 포함하는 리터럴 단어 또는 정규식 문자열을 검색할 수 있습니다. 하나의 문자를 나타낼 수 있음을 의미합니다. 예를 들어 "bad", "dad", "mad"와 같은 단어를 추가한 다음 search("pad") → false, search("bad") → true, search(".ad")를 검색합니다. → true 및 검색("b..") → true

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

처음에 insertNode()를 정의하는 몇 가지 방법이 있습니다. 이것은 헤드 참조와 문자열 s를 취하며 다음과 같이 작동합니다 -
curr :=헤드, n :=s의 크기
0 ~ n – 1 범위의 i에 대해
- x :=s[i]
- curr의 자식[x]가 null이 아닌 경우 curr의 자식[x] :=새 노드
- curr :=curr의 자식[x]
isEnd of curr을 true로 설정
addWord()에서 이 insertNode() 메소드를 호출하십시오.
check()라는 다른 메서드를 정의하면 curr, string s 및 index가 사용됩니다. 초기 인덱스는 0입니다. 이것은 다음과 같이 작동합니다 -
index =s의 크기이면 isEnd of curr을 반환합니다.
확인 설정 :=true
s[index]가 점이면
- 0에서 25 사이의 i에 대해
  - x :='a' + i의 ASCII
  - curr의 child[x] AND check(child[x] of curr, s, index + 1)이 true이면 true를 반환합니다.
그렇지 않으면
- x :=s[인덱스]
- curr의 child[x] AND check(child[x] of curr, s, index + 1)이 true이면 true를 반환합니다.
거짓 반환
검색 방식에서 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

출력