211. Design Add and Search Words Data Structure

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Solution

This problem asks us to build a word dictionary, which is obviously to use Trie. But it also asks to support dots '.' where dots can match any letter. Therefore, when we encounter '.', we need search all the children of the node until we find a matching string.

Trie

class WordDictionary {
    class TrieNode {
        private Map<Character, TrieNode> children = new HashMap<>();
        private char character;
        private boolean terminates = false;

        TrieNode() {
        }

        TrieNode(char character) {
            this.character = character;
        }

        void addWord(String word) {
            if (word == null || word.isEmpty()) return;

            char firstChar = word.charAt(0);
            TrieNode child = children.get(firstChar);
            if (child == null) {
                child = new TrieNode(firstChar);
                children.put(firstChar, child);
            }
            if (word.length() > 1) {
                child.addWord(word.substring(1));
            } else {
                child.setTerminates(true);
            }
        }

        boolean search(String word) {
            if (word == null || word.isEmpty()) return false;

            char firstChar = word.charAt(0);
            if (firstChar == '.') {
                String subWord = word.substring(1);
                if (subWord.isEmpty()) {
                    for (TrieNode child : children.values()) {
                        if (child.terminates) {
                            return true;
                        }
                    }
                } else {
                    for (TrieNode child : children.values()) {
                        if (child.search(subWord)) {
                            return true;
                        }
                    }
                }
            } else {
                if (children.containsKey(firstChar)) {
                    TrieNode child = children.get(firstChar);
                    if (word.length() == 1) {
                        return child.terminates;
                    } else {
                        return child.search(word.substring(1));
                    }
                }
            }
            return false;
        }

        void setTerminates(boolean terminates) {
            this.terminates = terminates;
        }
    }

    private TrieNode root = new TrieNode();

    public WordDictionary() {
    }
    
    public void addWord(String word) {
        root.addWord(word);
    }
    
    public boolean search(String word) {
        return root.search(word);
    }
}

Reference

• 211. Design Add and Search Words Data Structure, LeetCode.
• 211. Design Add and Search Words Data Structure, LeetCode Solutions.