1
class StreamChecker {
2

3
  class TrieNode {
4
    boolean isWord;
5
    TrieNode[] next = new TrieNode[26];
6
  }
7

8
  TrieNode root = new TrieNode();
9
  StringBuilder sb = new StringBuilder();
10

11
  public StreamChecker(String[] words) {
12
    createTrie(words);
13
  }
14

15
  public boolean query(char letter) {
16
    sb.append(letter);
17
    TrieNode node = root;
18
    for (int i = sb.length() - 1; i >= 0 && node != null; i--) {
19
      char ch = sb.charAt(i);
20
      node = node.next[ch - 'a'];
21
      if (node != null && node.isWord) {
22
        return true;
23
      }
24
    }
25
    return false;
26
  }
27

28
  private void createTrie(String words[]) {
29
    for (String s : words) {
30
      TrieNode node = root;
31
      int len = s.length();
32
      for (int i = len - 1; i >= 0; i--) {
33
        char ch = s.charAt(i);
34
        if (node.next[ch - 'a'] == null) {
35
          node.next[ch - 'a'] = new TrieNode();
36
        }
37
        node = node.next[ch - 'a'];
38
      }
39
      node.isWord = true;
40
    }
41
  }
42
}