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，

• x：= s [i]

• 如果curr的child [x-'a']不为空，则-

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

• curr.child [x-'a'] =创建一个新节点

• curr：=头

• 对于初始化i：= 0，当i <s的大小时，更新（将i增加1），执行-

• 的isEnd：= true

• 从初始化程序执行此操作

• insertNode（head，words [i]）

• head：=创建一个新节点

• 对于初始化i：= 0，当i <字长时，更新（将i增加1），执行-

• curr：=头

• 定义一个函数query()，这将需要x，

• curr：= waitList [i]

• 如果curr.child [x-'a']，则

• curr：= curr的子级[x-'a']

• 在临时结束时插入curr

• ret：= ret OR curr isEnd

• 将头插入waitList的末尾

• 使一个节点阵列成为临时节点

• 如果head.child [x-'a']，则-

• ret：=错误

• 对于初始化i：= 0，当i <waitList的大小时，更新（将i增加1），执行-

• 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