Back to DSA

Design Add and Search Words Data Structure

hard
Acceptance: 40%
TrieDFSDesignString

Create a dictionary data structure that supports two operations: addWord(word) stores a word, and search(pattern) returns true if any stored word matches the pattern. The pattern may contain the wildcard character '.', which can stand for any single letter.

Examples

Example 1:
Input:WordDictionary(), addWord('cat'), addWord('car'), addWord('bar'), search('.ar'), search('c..'), search('b.t')
Output:[null,null,null,null,true,true,false]

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumCheapest Flights Within K StopshardSurrounded RegionsmediumGraph Valid Treemedium
00:00
class WordDictionary {
    private WordDictionary[] children = new WordDictionary[26];
    private boolean isEnd = false;

    public void addWord(String word) {
        WordDictionary node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new WordDictionary();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return searchHelper(word, 0, this);
    }

    private boolean searchHelper(String word, int idx, WordDictionary node) {
        if (idx == word.length()) return node.isEnd;
        char c = word.charAt(idx);
        if (c == '.') {
            for (WordDictionary child : node.children) {
                if (child != null && searchHelper(word, idx + 1, child)) return true;
            }
            return false;
        }
        int ci = c - 'a';
        return node.children[ci] != null && searchHelper(word, idx + 1, node.children[ci]);
    }
}
Time complexityO(m) for addWord, O(26^m) worst case for search
Space complexityO(n * m)