Implement Trie (Prefix Tree) LeetCode solution in Java

1
class Trie {
2
  private class Node {
3
    char character;
4
    Node[] sub;
5

6
    Node(char c) {
7
      this.character = c;
8
      sub = new Node[26];
9
    }
10
  }
11

12
  Node root;
13
  HashMap<String, Boolean> map;
14

15
  public Trie() {
16
    root = new Node('\0');
17
    map = new HashMap<>();
18
  }
19

20
  public void insert(String word) {
21
    Node temp = root;
22
    for (char c : word.toCharArray()) {
23
      int index = c - 'a';
24
      if (temp.sub[index] == null) temp.sub[index] = new Node(c);
25

26
      temp = temp.sub[index];
27
    }
28
    map.put(word, true);
29
  }
30

31
  public boolean search(String word) {
32
    return map.containsKey(word);
33
  }
34

35
  public boolean startsWith(String prefix) {
36
    Node temp = root;
37
    for (char c : prefix.toCharArray()) {
38
      int index = c - 'a';
39
      if (temp.sub[index] == null) return false;
40
      temp = temp.sub[index];
41
    }
42
    return true;
43
  }
44
}