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

此題要我們建立一個 word dictionary，這很明顯就是要使用 Trie。不過題目還要求支援 dots '.'。在搜尋的時候，它可以匹配任何字元。因此，當遇到 '.' 的時候，我們必須要搜尋該 node 的所有 children，直到找到匹配的字串。

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);
    }
}

參考

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