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;

    }
}