Add and Search Word - Data structure design | Leetcode

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first. 

 

---

Solution: The difference between this algorithm and the basic trie algorithm is just in the way we handle the dots. When we see a dot, we take all the children of the current node, and check whether the remaining characters in the word can be found. If so, it is a match. If we have a dot and we get a TERMINAL node, then the word is not found since the trie search terminates halfway in the word.

public class WordDictionary {

    private static class TrieNode {
        private Map<Character, TrieNode> children = new HashMap<>();
    }
    
    private TrieNode root = new TrieNode();
    private static final char TERMINAL = (char) -1;
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode child = node.children.get(c);
            if (child == null) {
                child = new TrieNode();
                node.children.put(c, child);
            }
            node = child;
        }
        node.children.put(TERMINAL, node);
    }

    // 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 searchFrom(word, 0, root);
    }
    
    private boolean searchFrom(String word, int start, TrieNode node) {
        for (int i = start; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                return searchDot(word, i + 1, node);
            }
            node = node.children.get(c);
            if (node == null) {
                return false;
            }
        }
        return node.children.containsKey(TERMINAL);
    }
    
    private boolean searchDot(String word, int i, TrieNode node) {
        for (TrieNode child: node.children.values()) {
            // If we hit a terminal node, that means the word is not found.
            if (child == node) continue;
            
            if (searchFrom(word, i, child)) {
                return true;
            }
        }
        return false;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");