C++での文字のストリーム

次のようにStreamCheckerクラスを実装するとします-

• StreamChecker（words）-これはコンストラクターであり、指定された単語でデータ構造を初期化します。

• query（letter）-これは、k> =1の場合、クエリされた最後のk文字（クエリされたばかりの文字を含め、古いものから新しいものの順に）が指定されたリストの単語の1つを綴る場合にtrueを返します。

したがって、入力がword list =["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、

  が必要です。

  • curr：=ヘッド

  • 初期化i：=0の場合、i

    • x：=s [i]

    • currのchild[x-'a']がnullでない場合、-

      • curr.child[x-'a']=新しいノードノードを作成します

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

  • isEnd of curr：=true

• イニシャライザからこれを行います

  • head：=新しいノードを作成する

  • 初期化i：=0の場合、i <単語のサイズの場合、更新（iを1増やします）、実行-

    • insertNode（head、words [i]）

  • curr：=ヘッド

• 関数query（）を定義します。これにはxが必要です

  • ノードの1つの配列を一時的にします

  • head.child [x-'a']の場合、-

    • waitListの最後にヘッドを挿入します

  • ret：=false

  • 初期化i：=0の場合、i

    • curr：=waitList [i]

    • curr.child [x-'a']の場合、

      • curr：=currの子[x-'a']

      • 温度の最後にcurrを挿入します

      • ret：=ret OR isEnd of curr

  • swap（temp、waitList）

  • retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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