Trie Data Structure - Recursive Search ( LeetCode 211. Design Add and Search Words Data Structure) https://leetcode.com/problems/design-add-and-search-words-data-structure/)

trie.java

class Trie {

    TrieNode root;

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

    public TrieNode getRoot() {
        return root;
    }

    public void insert(String word) {
        TrieNode currNode = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!currNode.containsKey(c)) {
                currNode.put(c, new TrieNode());
            }
            currNode = currNode.get(c);
        }
        currNode.setEnd();
    }

    TrieNode searchPrefix(String word) {
        TrieNode currNode = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!currNode.containsKey(c)) {
                return null;
            }
            currNode = currNode.get(c);
        }
        return currNode;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    public boolean genSearch(char[] chars, int idx, TrieNode currNode) {
        // edge case: if the trie is consumed before the word is consume???
        if (idx < chars.length && currNode == null) return false;

        // base case: word consumed
        if (idx >= chars.length) return true;

        char currChar = chars[idx];
        // char found: success and next
        if (currNode != null && currNode.containsKey(currChar)) {
            return genSearch(chars, idx + 1, currNode.get(currChar));
        }

        // dot found: consume next (unless next is null)
        if (currChar == '.' && currNode != null) {
            for (int j = 0; j < currNode.numChildren(); j++) {
                // any filled link from currNode
                if (currNode.get(j) != null) {
                    // the branch consumed the reminder successfully?
                    if (genSearch(chars, idx + 1, currNode.get(j))) {
                        return true;
                    }
                }
            }
        }

        // else
        return false;
    }

    private class TrieNode {
        final int R = 128;
        char value;
        boolean isEndKey;
        TrieNode[] children;

        public TrieNode() {
            children = new TrieNode[R];
        }
        public boolean containsKey(int c) {
            return children[c] != null;
        }
        public TrieNode get(int c) {
            return children[c];
        }
        public void put(int c, TrieNode node) {
            children[c] = node;
        }
        public void setEnd() {
            isEndKey = true;
        }
        public boolean isEnd() {
            return isEndKey;
        }
        public int numChildren() {
            return R;
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
class WordDictionary {

    Trie trie;

    public WordDictionary() {
        trie = new Trie();
    }

    public void addWord(String word) {
        trie.insert(word);
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        return trie.genSearch(chars, 0, trie.getRoot());
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */