1032. 字符流

approach 1，trie树

class StreamChecker {
    class Trie {
        Trie[] next = new Trie[26];
        boolean end = false;

        private void insert(String word) {
            char[] cs = word.toCharArray();
            Trie nx = this;
            for (int i = word.length() - 1; i >= 0; i--) {
                int c = word.charAt(i) - 'a';
                if (nx.next[c] == null) {
                    nx.next[c] = new Trie();
                }
                nx = nx.next[c];
            }
            nx.end = true;
        }
    }

    List<Integer> list = new ArrayList<>();
    Trie trie = new Trie();
    public StreamChecker(String[] words) {
        for (String w : words) {
            trie.insert(w);
        }
    }
    
    public boolean query(char letter) {
        list.add(letter - 'a');
        int n = list.size();
        Trie nx = trie;
        for (int i = n - 1; i >= 0; i--) {
            int c = list.get(i);
            if (nx.next[c] == null) {
                return false;
            } else if (nx.next[c].end) {
                return true;
            } else {
                nx = nx.next[c];
            }
        }
        return false;
    }
}