# Trie Tree java solution! very easy to understand!

• This solution uses Trier tree and DFS to search '.' case.

``````1, first build the standard trier tree root.
2, add the word into the tree.
3, basic search for normal character 'a'-'z' and DFS for the '.'
``````

Here is the solution, it is fast that beat 80%-90% solutions.

``````public class WordDictionary {

// Adds a word into the data structure.
Trier root = new Trier();
Trier pointer = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (pointer.children[c-'a'] == null) {
pointer.children[c-'a'] = new Trier();
pointer = pointer.children[c-'a'];
} else {
pointer = pointer.children[c-'a'];
}
}
pointer.flag = true;
}

// 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) {
Trier pointer = root;
return helper(word,0,pointer);
}
private boolean helper(String word, int start, Trier cur) {
if (start == word.length()) {
if (cur.flag) {
return true;
} else {
return false;
}
}
char c = word.charAt(start);
if (c == '.') {
for (int i = 0; i < 26; i++) {
if (cur.children[i] != null) {
if (helper(word,start+1,cur.children[i])) {
return true;
}
}
}
} else {
if (cur.children[c-'a'] == null) {
return false;
} else {
return helper(word,start+1,cur.children[c-'a']);
}
}
return false;
}
class Trier {
Trier[] children;
char c;
boolean flag;
public Trier() {
children = new Trier[26];
flag = false;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.