Design Add and Search Words Data Structure LeetCode solution in Java

1
class WordDictionary {
2
  private class Node {
3
    boolean last;
4
    Node[] sub;
5

6
    Node() {
7
      last = false;
8
      sub = new Node[26];
9
    }
10
  }
11

12
  Node root;
13

14
  public WordDictionary() {
15
    root = new Node();
16
  }
17

18
  public void addWord(String word) {
19
    Node temp = root;
20
    for (char c : word.toCharArray()) {
21
      int index = c - 'a';
22
      if (temp.sub[index] == null) temp.sub[index] = new Node();
23
      temp = temp.sub[index];
24
    }
25
    temp.last = true;
26
  }
27

28
  public boolean search(String word) {
29
    Node temp = root;
30
    return dfs(temp, word, 0);
31
  }
32

33
  private boolean dfs(Node node, String word, int i) {
34
    if (i == word.length()) return node.last;
35

36
    int index = word.charAt(i) - 'a';
37
    if (word.charAt(i) == '.') {
38
      for (int j = 0; j < 26; j++) {
39
        if (node.sub[j] != null) if (dfs(node.sub[j], word, i + 1)) return true;
40
      }
41
      return false;
42
    } else if (node.sub[index] == null) return false;
43
    return dfs(node.sub[index], word, i + 1);
44
  }
45
}