C++의 문자 스트림

다음과 같이 StreamChecker 클래스를 구현한다고 가정합니다. -

• StreamChecker(words) - 생성자이며 주어진 단어로 데이터 구조를 초기화합니다.

• query(letter) - 일부 k>=1에 대해 쿼리된 마지막 k개 문자(방금 쿼리된 이 문자를 포함하여 가장 오래된 것부터 최신 순으로)가 주어진 목록에 있는 단어 중 하나의 철자일 때 true를 반환합니다.

따라서 입력이 단어 목록 =["ce", "g", "lm"]과 같으면 [a,b,c,e,f,g,h,i,j,k에 대해 쿼리를 여러 번 호출합니다. ,l,m], 출력은 e, g, m에 대해 true이고 다른 항목에 대해 false가 됩니다.

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

• 노드 구조를 정의하고 26개의 노드로 구성된 배열이 있으며 isEnd 플래그

• 초기에 isEnd는 false이고 자식 배열은 null로 채워집니다.

• 노드 헤드 정의

• 노드 배열을 waitList로 만들기

• insertNode() 함수를 정의하면 head, s,

  가 사용됩니다.

  • 커 :=머리

  • for initialize i :=0, i

    • x :=s[i]

    • curr의 자식[x - 'a']가 null이 아니면 -

      • curr.child[x - 'a'] =새 노드 생성 Node

    • curr :=curr.child[x - 'a']

  • isEnd of curr :=true

• 이니셜라이저에서 다음을 수행합니다.

  • head :=새 노드 생성

  • for initialize i :=0, i <단어 크기일 때 업데이트(i 1 증가), −

    • insertNode(머리, 단어[i])

  • 커 :=머리

• 함수 query()를 정의하면 x가 필요합니다.

  • 하나의 노드 배열을 임시로 만듭니다.

  • head.child[x - 'a']이면 -

    • waitList 끝에 헤드 삽입

  • ret :=거짓

  • for initialize i :=0, i

    • curr :=대기 목록[i]

    • curr.child[x - 'a']인 경우

      • curr :=curr의 자식[x - 'a']

      • temp의 끝에 curr 삽입

      • ret :=ret OR isEnd of curr

  • 스왑(임시, 대기자 명단)

  • 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
struct Node {
   Node* child[26];
   bool isEnd;
   Node(){
      isEnd = false;
      for (int i = 0; i < 26; i++)
      child[i] = NULL;
   }
};
class StreamChecker {
   public:
   Node* head;
   vector<Node*> waitList;
   void insertNode(Node* head, string& s){
      Node* curr = head;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!curr->child[x - 'a']) {
            curr->child[x - 'a'] = new Node();
         }
         curr = curr->child[x - 'a'];
      }
      curr->isEnd = true;
   }
   StreamChecker(vector<string>& words){
      head = new Node();
      for (int i = 0; i < words.size(); i++) {
         insertNode(head, words[i]);
      }
      Node* curr = head;
   }
   bool query(char x){
      vector<Node*> temp;
      if (head->child[x - 'a']) {
         waitList.push_back(head);
      }
      bool ret = false;
      for (int i = 0; i < waitList.size(); i++) {
         Node* curr = waitList[i];
         if (curr->child[x - 'a']) {
            curr = curr->child[x - 'a'];
            temp.push_back(curr);
            ret |= curr->isEnd;
         }
      }
      swap(temp, waitList);
      return ret;
   }
};
main(){
   vector<string> v = {"ce","g","lm"};
   StreamChecker ob(v);
   cout << (ob.query('a')) << endl;
   cout << (ob.query('b')) << endl;
   cout << (ob.query('c')) << endl;
   cout << (ob.query('e')) << endl;
   cout << (ob.query('f')) << endl;
   cout << (ob.query('g')) << endl;
   cout << (ob.query('h')) << endl;
   cout << (ob.query('i')) << endl;
   cout << (ob.query('j')) << endl;
   cout << (ob.query('k')) << endl;
   cout << (ob.query('l')) << endl;
   cout << (ob.query('m'));
}

입력

"ce","g","lm", query(),

출력

0 0 0 1 0 1 0 0 0 0 0 1