Design Add and Search Words Data Structure medium

Problem Statement

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.
• addWord(word) Adds word to the data structure.
• 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 1

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

Example 2

Input
["WordDictionary","addWord","search"]
[[],["a"],["."]]
Output
[null,null,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("a");
wordDictionary.search("."); // return True

Steps

1. Data Structure: We'll use a Trie (prefix tree) to efficiently store and search words. A Trie is particularly well-suited for this problem because it allows for prefix-based searches.

2. Trie Node: Each node in the Trie will represent a character in a word. It will have:

   • children: A map to store child nodes (next characters).
   • isWordEnd: A boolean to indicate if the word ends at this node.

3. addWord(word): Iterate through the word, adding nodes to the Trie as needed. Mark isWordEnd as true for the last node.

4. search(word): This is the more complex part. We'll recursively traverse the Trie.

   • If a character is a letter, we follow the corresponding child node.
   • If a character is a '.', we recursively explore all child nodes.
   • If we reach the end of the word and isWordEnd is true, we've found a match.

Explanation

The Trie efficiently handles both adding words and searching for words with wildcards ('.'). Adding a word involves traversing the Trie and adding nodes for each character. Searching with wildcards requires exploring multiple branches of the Trie, but the Trie's structure ensures that this exploration is efficient (avoiding unnecessary checks).

Code

class TrieNode {
    children: Map<string, TrieNode>;
    isWordEnd: boolean;

    constructor() {
        this.children = new Map();
        this.isWordEnd = false;
    }
}

class WordDictionary {
    root: TrieNode;

    constructor() {
        this.root = new TrieNode();
    }

    addWord(word: string): void {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char)!;
        }
        node.isWordEnd = true;
    }

    search(word: string): boolean {
        return this.searchHelper(word, this.root);
    }

    searchHelper(word: string, node: TrieNode): boolean {
        if (word.length === 0) {
            return node.isWordEnd;
        }

        const char = word[0];
        if (char === '.') {
            for (const child of node.children.values()) {
                if (this.searchHelper(word.substring(1), child)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node.children.has(char)) {
                return false;
            }
            return this.searchHelper(word.substring(1), node.children.get(char)!);
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

Complexity

• Time Complexity:

  • addWord: O(m), where m is the length of the word.
  • search: In the worst case (many dots and many words), it could be O(n * 4^m), where n is the number of words in the dictionary and m is the length of the search word. However, in practice, it's often much faster due to the Trie's structure.

• Space Complexity: O(n * m), where n is the number of words added and m is the average length of a word (due to the Trie's storage).