本文主要是介绍leetcode 1032. Stream of Characters，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode 1032. Stream of Characters
题意：如果你稍微了解关于大数据/视频/音频流(Stream)处理的背景的话，你会觉得这道题非常棒。简单介绍下流处理，举个简单的例子，你在Youtobe上观看电影的时候不需要事先下载整个电影文件，而是进行缓存加载，来一点播放一点。前端视频代码需要对最近收到的视频文件进行检测，就要用到这个StreamChecker。
在这道题中，会大量进行Query，所以查询必须用Tri树的数据结构进行优化，在构造函数中做这件事。
query的描述我看了好久才明白什么意思，
- query(letter): returns true if and only if for somek >= 1, the lastk` characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.
它指的是当收到一个letter的时候，查看最近收到的letter流的末尾是不是存在指定的单词，例如收到query('a'), query('b'), query('c')之后，letter流就是"abc", 我们只需要检测["c","bc","abc"]中是否有指定单词。
思路：简单字典树。
代码：
struct Node
{int next[500010][26], fail[500010], end[500010];int root, L;int newnode(){for (int i = 0; i < 26; i++)next[L][i] = -1;end[L++] = 0;return L - 1;}void insert(const char* buf){int len = strlen(buf);int now = root;for (int i = len-1; i >= 0; i--){if (next[now][buf[i] - 'a'] == -1)next[now][buf[i] - 'a'] = newnode();now = next[now][buf[i] - 'a'];}end[now]++;}void init(){L = 0;root = newnode();}
};class StreamChecker {
public:StreamChecker(vector<string>& words) {Tri.init();for (int i = 0; i < words.size(); i++)Tri.insert(words[i].c_str());}bool query(char letter) {s += letter;int now = Tri.root;for (int i = s.length() - 1; i >= 0; i--){int next = Tri.next[now][s[i] - 'a'];if (next == -1) break;now = next;if (Tri.end[now] != 0) return true;}return false;}string s;Node Tri;
};
这篇关于leetcode 1032. Stream of Characters的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
