CareerCup

We can create a Ternary search tree Or a Trie structure for dictionary word.
And can find out the words starting with part before *.
Later filter these words with the end part of the pattern.

we can use dictionaries for this..where key is D*sk and we can get the value for * dynamically. Then match for the word in dictionary.

/*
use a Trie structure where each node has a character and has a list of nodes.
*/

// iterative
class WordDictionary {
    class Node {
        Node[] letters;
        boolean endOfWord;
        
        public Node() {
            letters = new Node[26];
            endOfWord = false;
        }
    }

    Node head;

    /** Initialize your data structure here. */
    public WordDictionary() {
        head = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        if (word == null) {
            return;
        }
        
        Node temp = head;
        
        for (int i = 0; i < word.length(); ++i) {
            if (temp.letters[word.charAt(i) - 'a'] == null) {
                temp.letters[word.charAt(i) - 'a'] = new Node();
            }
            
            temp = temp.letters[word.charAt(i) - 'a'];
            
            if (i == word.length() - 1) {
                temp.endOfWord = true;
            }
        }
        
        return;
    }
    
    /** 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) {
        if (word == null) {
            return false;
        }
        
        // bfs - iterative
        Queue<Node> q = new LinkedList<>();
        q.add(head);
        
        for (int i = 0; i < word.length(); ++i) {
            int size = q.size();
            if (size == 0) {
                return false;
            }
            
            if (word.charAt(i) == '.') {
                while (size > 0) {
                    Node temp = q.remove();
                    Node[] tempLetters = temp.letters;
                    
                    for (Node letter : tempLetters) {
                        if (letter != null) {
                            q.add(letter);
                        }
                    }
                    
                    --size;
                }
            }
            else {
                while (size > 0) {
                    Node temp = q.remove();
                    Node[] tempLetters = temp.letters;
                    
                    if (tempLetters[word.charAt(i) - 'a'] != null) {
                        q.add(tempLetters[word.charAt(i) - 'a']);
                    }
                    
                    --size;
                }
            }
        }
        
        while (!q.isEmpty()) {
            Node temp = q.remove();
            
            if (temp.endOfWord) {
                return true;
            }
        }
        
        return false;
    }
}

// recursive
class WordDictionary {
    class Node {
        Node[] letters;
        boolean endOfWord;
        
        public Node() {
            letters = new Node[26];
            endOfWord = false;
        }
    }

    Node head;

    /** Initialize your data structure here. */
    public WordDictionary() {
        head = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        if (word == null) {
            return;
        }
        
        addWordUtil(word, 0, word.length() - 1, head);
        
        return;
    }

    public void addWordUtil(String word, int currIdx, int endIdx, Node n) {
        if (currIdx < endIdx) {
            if (n.letters[word.charAt(currIdx) - 'a'] == null) {
                n.letters[word.charAt(currIdx) - 'a'] = new Node();
            }
            addWordUtil(word, currIdx + 1, endIdx, n.letters[word.charAt(currIdx) - 'a']);
        }
        else if (currIdx == endIdx) {
            if (n.letters[word.charAt(currIdx) - 'a'] == null) {
                n.letters[word.charAt(currIdx) - 'a'] = new Node();
            }
            n.letters[word.charAt(currIdx) - 'a'].endOfWord = true;
        }
        
        return;
    }
    
    /** 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) {
        if (word == null) {
            return false;
        }
        
        // dfs - recursive
        return searchUtil(word, 0, word.length() - 1, head);
    }
    
    public boolean searchUtil(String word, int currIdx, int endIdx, Node currNode) {
        if (currIdx < endIdx) {
            if (word.charAt(currIdx) == '.') {
                for (Node letter : currNode.letters) {
                    if (letter != null && searchUtil(word, currIdx + 1, endIdx, letter)) {
                        return true;
                    }
                }
            }
            else {
                if (currNode.letters[word.charAt(currIdx) - 'a'] == null) {
                    return false;
                }
                else {
                    return searchUtil(word, currIdx + 1, endIdx, currNode.letters[word.charAt(currIdx) - 'a']);
                }
            }
        }
        else if (currIdx == endIdx) {
            if (word.charAt(currIdx) == '.') {
                for (Node letter : currNode.letters) {
                    if (letter != null && letter.endOfWord) {
                        return true;
                    }
                }
            }
            else {
                if (currNode.letters[word.charAt(currIdx) - 'a'] != null && currNode.letters[word.charAt(currIdx) - 'a'].endOfWord) {
                    return true;
                }
            }
        }
        
        return false;
    }
}