My JAVA Trie based solution

• public class WordDictionary {
WordNode root = new WordNode();
public void addWord(String word) {
char chars[] = word.toCharArray();
}

private void addWord(char[] chars, int index, WordNode parent) {
char c = chars[index];
int idx = c-'a';
WordNode node = parent.children[idx];
if (node == null){
node = new WordNode();
parent.children[idx]=node;
}
if (chars.length == index+1){
node.isLeaf=true;
return;
}
}

public boolean search(String word) {
return search(word.toCharArray(), 0, root);
}

private boolean search(char[] chars, int index, WordNode parent){
if (index == chars.length){
if (parent.isLeaf){
return true;
}
return false;
}
WordNode[] childNodes = parent.children;
char c = chars[index];
if (c == '.'){
for (int i=0;i<childNodes.length;i++){
WordNode n = childNodes[i];
if (n !=null){
boolean b = search(chars, index+1, n);
if (b){
return true;
}
}
}
return false;
}
WordNode node = childNodes[c-'a'];
if (node == null){
return false;
}
return search(chars, ++index, node);
}

private class WordNode{
boolean isLeaf;
WordNode[] children = new WordNode[26];
}
}

• don't you think time complexity is too large, max time complexity will be O(26^n)

• It only checks all 26 letters in case of '.'
In theory you could construct a search string consisting only of '.' characters, and make the search string longer than any word in a trie. In this case every single node will be searched.
It would still be A LOT less then O(26^n) as it's imporbable that every node has a fully filled set of child nodes.

• Thanks for sharing. Could be shorter

public class WordDictionary {
class TrieNode {
TrieNode[] child = new TrieNode[26];
boolean isWord = false;
}
TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
if (p.child[c - 'a'] == null) p.child[c - 'a'] = new TrieNode();
p = p.child[c - 'a'];
}
p.isWord = true;
}

public boolean search(String word) {
return helper(word, 0, root);
}

private boolean helper(String s, int index, TrieNode p) {
if (index >= s.length()) return p.isWord;
char c = s.charAt(index);
if (c == '.') {
for (int i = 0; i < p.child.length; i++)
if (p.child[i] != null && helper(s, index + 1, p.child[i]))
return true;
return false;
} else return (p.child[c - 'a'] != null && helper(s, index + 1, p.child[c - 'a']));
}
}

• @EdickCoding Very nice and short! I think my helper() as below is clean too. Thanks for sharing :)

private boolean doSearch(TrieNode cur, char[] word, int pos) {
if (cur == null) return false;
if (pos == word.length) return cur.isWord;

if (word[pos] == '.') {
for (TrieNode next : cur.next)
if (doSearch(next, word, pos + 1))
return true;
return false;
}
return doSearch(cur.next[word[pos] - 'a'], word, pos + 1);
}

• public class WordDictionary {
TrieNode root;

public WordDictionary() {
root = new TrieNode();
}

public void addWord(String word) {
if (word == null || word.isEmpty()) {
return;
}
TrieNode cur = root;

for (char c: word.toCharArray()) {
if (cur.children[c-'a'] != null) {
cur = cur.children[c-'a'];
} else {
cur.children[c-'a'] = new TrieNode(c);
cur = cur.children[c-'a'];
}
}

cur.isLeaf = true;
}

public boolean search(String word) {
if (word == null || word.isEmpty()) {
return false;
}
return find(root, word);
}

public boolean find (TrieNode cur, String word) {
for (int i = 0; i<word.length(); i++) {
char c = word.charAt(i);
if (c == '.') {
for (int j=0; j<26; j++) {
if(find(cur, (char)('a' + j) + word.substring(i+1))) {
return true;
}
}
return false;
} else if (cur.children[c-'a'] != null) {
cur = cur.children[c-'a'];
} else {
return false;
}
}

return cur.isLeaf;
}

class TrieNode {
char c;
boolean isLeaf;
TrieNode[] children = new TrieNode[26];
TrieNode() {}
TrieNode(char c) {
this.c = c;
}
}

}

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