JAVA程序设计：字符流（LeetCode：1032）

按下述要求实现 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;

    }
}