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：=retORcurrisEnd
将头插入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