class StreamChecker {

    private Trie trie = new Trie();
    private LinkedList<Character> queries = new LinkedList<Character>();

    public StreamChecker(String[] words) {

        for(String word : words) {
            char[] reverse = new char[word.length()];
            for (int i = word.length() - 1; i >= 0; i--) {
                reverse[word.length() - i - 1] = word.charAt(i);
            }
            trie.insert(new String(reverse), 0);
        }
    }

    public boolean query(char letter) {
        queries.add(letter);
        return queryInternal(this.trie, queries.size() - 1);
    }

    public boolean queryInternal(Trie t, Integer index) {
        if (index < 0) {
            return false;
        }

        Trie current = t.getTrie(queries.get(index));
        if (current == null) {
            return false;
        }

        if (current.completesWord) {
            return true;
        }

        return queryInternal(current, --index);
    }

    private class Trie {

        private Map<Character, Trie> children;
        private boolean completesWord = false;

        public Trie() {
            children = new HashMap<>();
        }

        public void insert(String s, int index) {
            Trie child = this.children.computeIfAbsent(s.charAt(index), (x) -> new Trie());
            if (s.length() == index + 1) {
                child.completesWord = true;
                return;
            }

            child.insert(s, ++index);
        }

        public Trie getTrie(Character c) {
            return this.children.get(c);
        }
    }
}