LeetCode 1032 - Stream of Characters

https://leetcode.com/problems/stream-of-characters/

Implement the StreamChecker class as follows:

• StreamChecker(words): Constructor, init the data structure with the given words.
• query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

Note:

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 2000
• Words will only consist of lowercase English letters.
• Queries will only consist of lowercase English letters.
• The number of queries is at most 40000.

X. Trie
用字典树即可解决。首先在init的时候，把words中所有word逆置后存入字典树中；在query的时候，也有逆序的方式记录所有历史query过的值，同时判断其前缀是否存在于字典树中即可

https://www.cnblogs.com/rookielet/p/10746719.html

看到这个题很快想到了该用前缀树trie来存下单词表，但是此题因为是要判断以query传入的当前字母结尾的单词是否出现在单词表中，要倒序存。

而此题的关键也是倒序存和倒序的查找，在trie的基础上稍微修改代码即可完成。

class StreamChecker {
    class Node{
        Node[] children;
        boolean endOfWord;
        public Node() {
            children = new Node[26];
            endOfWord = false;
        }
    }

    Node root;
    StringBuilder sb;

    private void insert(String word) {
        Node cur = root;
        for(int i = word.length() - 1; i >= 0; i--) {
            char ch = word.charAt(i);
            Node next = cur.children[ch - 'a'];
            if(next == null) {
                cur.children[ch - 'a'] = next = new Node();
            }
            cur = next;
        }
        cur.endOfWord = true;
    }

    public StreamChecker(String[] words) {
        root = new Node();
        sb = new StringBuilder();
        for(String word : words) {
            insert(word);
        }
    }

    public boolean query(char letter) {
        boolean res = false;

        sb.append(letter);
        Node cur = root;
        for(int i = sb.length() - 1; i >= 0; i--) {
            char ch = sb.charAt(i);
            if(cur.children[ch - 'a'] == null) {
                return false;
            }
            cur = cur.children[ch - 'a'];
            if(cur.endOfWord) return true;
        }

        return false;
    }
}

(AC 自动机) $O(N+Q)$

1. AC 自动机模板题，这里只简要说明一下 AC 自动机的思想。
2. 首先根据所有的模式串构建 Trie （字典）树，然后通过宽度优先遍历在 Trie 树上构建失败指针，即如果当前边匹配失败，该回到哪里重新匹配。这里的思想类似于 KMP 的思想。
3. 这里需要注意的是，在宽度优先遍历的过程中，需要将 Trie 树中，标记为是单词终点的结点通过失败指针进行继承。

时间复杂度

• 假设 N 为字典树中的结点个数，Q 为总的询问长度，时间复杂度为 $O(N+Q)$。

空间复杂度

• 需要存储字典树，故空间复杂度为 $O(N)$。

https://www.acwing.com/solution/LeetCode/content/1852/

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