Trie t = new Trie();

/** Initialize your data structure here. */

public WordDictionary() {

}

/** Adds a word into the data structure. */

public void addWord(String word) {

add(t, word.toCharArray(), 0);

}

private static void add(Trie tr, char[] chars, int i) {

while (i < chars.length) tr = tr.add(chars[i++]);

tr.isWord = true;

}

// private static void add(Trie tr, char[] chars, int i) {

// if (i >= chars.length) {

// tr.isWord = true;

// return;

// }

// add(tr.add(chars[i]), chars, i+1);

// }

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */

public boolean search(String word) {

return search(t, word.toCharArray(), 0);

}

private static boolean search(Trie tr, char[] chars, int i) {

while (i < chars.length) {

char c = chars[i];

if (c == '.') {

for (char nc: tr.map.keySet()) {

if (tr.has(nc) && search(tr.get(nc), chars, i+1)) {

return true;

}

}

return false;

} else {

if (!tr.has(c)) return false;

tr = tr.get(c);

i++;

}

}

return tr.isWord;

}

// private static boolean search(Trie tr, char[] chars, int i) {

// if (i >= chars.length) return tr.isWord;

// char c = chars[i];

// if (c == '.') {

// for (char nc: tr.map.keySet()) {

// if (tr.has(nc) && search(tr.get(nc), chars, i+1)) {

// return true;

// }

// }

// return false;

// } else {

// return tr.has(c) && search(tr.get(c), chars, i+1);

// }

// }

// also Trie[] map = new Trie[26];

Map<Character, Trie> map = new HashMap<>();

boolean isWord = false;

public Trie() {

}

public Trie get(char c) {

return this.map.get(c);

}

public Trie add(char c) {

return this.map.computeIfAbsent(c, cc -> new Trie());

}

public boolean has(char c) {

return c == '.' || this.map.containsKey(c);

}