按下述要求实现 StreamChecker 类：
StreamChecker(words)：构造函数，用给定的字词初始化数据结构。 query(letter)：如果存在某些 k >= 1，可以用查询的最后 k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。
示例：
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典 streamChecker.query('a'); // 返回 false streamChecker.query('b'); // 返回 false streamChecker.query('c'); // 返回 false streamChecker.query('d'); // 返回 true，因为 'cd' 在字词表中 streamChecker.query('e'); // 返回 false streamChecker.query('f'); // 返回 true，因为 'f' 在字词表中 streamChecker.query('g'); // 返回 false streamChecker.query('h'); // 返回 false streamChecker.query('i'); // 返回 false streamChecker.query('j'); // 返回 false streamChecker.query('k'); // 返回 false streamChecker.query('l'); // 返回 true，因为 'kl' 在字词表中。
提示：
1 <= words.length <= 2000 1 <= words[i].length <= 2000 字词只包含小写英文字母。 待查项只包含小写英文字母。 待查项最多 40000 个。
思路：由于待查项很大，我们并不能用传统的查询方式来做，因此我们可以考虑一波字典树，相信学过字典树的同学都对字典树的性质有所了解，字典树对于字符串的前缀查询有着非常好的性质。对于本题，由于题目要求我们只能匹配待查字符组成的串的后缀。我们可以考虑将查询表中的字符串倒着插入到字典树中，在查询时，我们可以将当前待查串从后往前在树上看是否存在一个后缀。
class StreamChecker { class node { boolean flag; node[] next; public node() { flag = false; next = new node[26]; } } node root; StringBuilder str; public StreamChecker(String[] words) { root = new node(); str = new StringBuilder(); for (int i = 0; i < words.length; i++) { node now = root; int len = words[i].length(); for (int j = len - 1; j >= 0; j--) { int k = words[i].charAt(j) - 'a'; if (now.next[k] == null) now.next[k] = new node(); now = now.next[k]; } now.flag = true; } } public boolean query(char letter) { str.append(letter); node now = root; for (int i = str.length() - 1; i >= 0; i--) { int k = str.charAt(i) - 'a'; if (now.next[k] != null) { now = now.next[k]; if (now.flag) return true; } else return false; } return false; } }
