题目

题解

思路一：字典树

class Trie {
    Trie[] children = new Trie[26];
    boolean isEnd = false;

    public void insert(String w) {
        Trie node = this;
        for (int i = w.length() - 1; i >= 0; --i) {
            int idx = w.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean query(StringBuilder s) {
        Trie node = this;
        //题目给的单词的最大长度是200，所以这里最多往前取200个字符的后缀，
        //这里也可以提前求出单词的最大长度，最多取最大长度的后缀
        for (int i = s.length() - 1, j = 0; i >= 0 && j < 201; --i, ++j) {
            int idx = s.charAt(i) - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
            if (node.isEnd) {
                return true;
            }
        }
        return false;
    }
}

class StreamChecker {
    //需要一个StringBuilder记录已经出现的字符
    private StringBuilder sb = new StringBuilder();
    private Trie trie = new Trie();

    public StreamChecker(String[] words) {
        for (String w : words) {
            trie.insert(w);
        }
    }

    public boolean query(char letter) {
        sb.append(letter);
        return trie.query(sb);
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker obj = new StreamChecker(words);
 * boolean param_1 = obj.query(letter);
 */

思路二：字典树+AC自动机

思路一中需要一个StringBuilder记录已经出现的字符，实际上在字典树中构建AC自动机就可以去掉这个StringBuilder,AC自动机实际上是KMP思想+字典树的结合，当匹配时候的时候，可以不用回到root节点重新开始匹配，而是增加了失败指针，跳转到失败指针的继续匹配，提升性能。

class StreamChecker {
    TrieNode root;
    TrieNode temp;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (cur.getChild(index) == null) {
                    cur.setChild(index, new TrieNode());
                }
                cur = cur.getChild(index);
            }
            cur.setIsEnd(true);
        }
        //构建失败指针
        root.setFail(root);
        Queue<TrieNode> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if(root.getChild(i) != null) {
                //root直接子节点匹配失败，则回到root节点，从头开始匹配
                root.getChild(i).setFail(root);
               //root直接子节点加入队列，后面的while循环，需要进一步构建
               //其他间接子节点的失败指针
                q.add(root.getChild(i));
            } else {
                //没有子节点也是回到root重新开始匹配
                root.setChild(i, root);
            }
        }
        while (!q.isEmpty()) {
            TrieNode node = q.poll();
            node.setIsEnd(node.getIsEnd() || node.getFail().getIsEnd());
            for (int i = 0; i < 26; i++) {
                if(node.getChild(i) != null) {
                    //设置子节点的失败指针为父节点的失败指针的子节点(公共前缀思想)
                    node.getChild(i).setFail(node.getFail().getChild(i));
                    //加入队列，继续构建子节点的失败指针
                    q.offer(node.getChild(i));
                } else {
                    //当匹配失败，也就是child为null的时候，从失败指针的地方继续匹配
                    node.setChild(i, node.getFail().getChild(i));
                }
            }
        }

        temp = root;
    }

    public boolean query(char letter) {
        temp = temp.getChild(letter - 'a');
        return temp.getIsEnd();
    }
}

class TrieNode {
    TrieNode[] children;
    boolean isEnd;
    TrieNode fail;

    public TrieNode() {
        children = new TrieNode[26];
    }

    public TrieNode getChild(int index) {
        return children[index];
    }

    public void setChild(int index, TrieNode node) {
        children[index] = node;
    }

    public boolean getIsEnd() {
        return isEnd;
    }

    public void setIsEnd(boolean b) {
        isEnd = b;
    }

    public TrieNode getFail() {
        return fail;
    } 

    public void setFail(TrieNode node) {
        fail = node;
    } 
}