211. Design Add and Search Words Data Structure

Description

The WordDictionary class implements a data structure that supports adding new words and searching for words, including the ability to use wildcard characters (.) that can match any letter.

Intuition

The primary intuition behind this problem is to use a Trie (prefix tree) to efficiently store and search for words. A Trie allows for fast insertion and lookup operations, making it suitable for handling words and their prefixes.

Approach

1. TrieNode Class: - Represents each node in the Trie. - Contains a dictionary children to store child nodes and a boolean isEndOfWord to mark the end of a word.
2. WordDictionary Class: - Initializes the Trie with a root TrieNode. - addWord method adds a word to the Trie by iterating through each character of the word and creating nodes as necessary. - search method performs a depth-first search (DFS) to handle the wildcard character .: - If the current character is ., it recursively checks all possible child nodes. - If the character matches, it moves to the next level in the Trie. - If the end of the word is reached, it checks if the current node marks the end of a word.

Complexity

Time Complexity:

• addWord: O(n), where n is the length of the word being added. This is because each character of the word is processed once.
• search: O(m * n), where m is the number of nodes in the Trie and n is the length of the word being searched. The worst case occurs when every character in the word is a wildcard, leading to a full traversal of the Trie.

Space Complexity:

• The space complexity is primarily determined by the number of nodes in the Trie. In the worst case, the Trie could have a node for every character in every word added, leading to a space complexity of O(N * L), where N is the number of words and L is the average length of the words.

Code

C++

class WordDictionary {
public:
    WordDictionary() {
        // Constructor
    }
    
    void addWord(string word) {
        wordsSet.insert(word);
    }
    
    bool search(string word) {
        for (const string& savedWord : wordsSet) {
            if (savedWord.length() != word.length()) continue;

            bool wordsMatch = true;
            for (int i = 0; i < word.length(); i++) {
                if (word[i] != '.' && savedWord[i] != word[i]) {
                    wordsMatch = false;
                    break;
                }
            }
            if (wordsMatch) return true;
        }
        return false;
    }

private:
    unordered_set wordsSet;
};

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEndOfWord = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.isEndOfWord
            if word[i] == '.':
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
            elif word[i] in node.children:
                return dfs(node.children[word[i]], i + 1)
            return False

        return dfs(self.root, 0)

Java

class WordDictionary {

    private List wordsList;

    public WordDictionary() {
        wordsList = new ArrayList<>();
    }
    
    public void addWord(String word) {
        wordsList.add(word);
    }
    public boolean search(String word) {
        for (String savedWord : wordsList) {
            if (savedWord.length() != word.length()) continue;

            boolean wordsMatch = true;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) != '.' && savedWord.charAt(i) != word.charAt(i)) {
                    wordsMatch = false;
                    break;
                }
            }
            if (wordsMatch) return true;
        }
        return false;
    }
}

JavaScript

var WordDictionary = function() {
    this.wordsSet = new Set();
};
/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    this.wordsSet.add(word);
};

WordDictionary.prototype.search = function(word) {
    for (const savedWord of this.wordsSet) {
        if (savedWord.length !== word.length) continue;

        let wordsMatch = true;
        for (let i = 0; i < word.length; i++) {
            if (word[i] !== '.' && savedWord[i] !== word[i]) {
                wordsMatch = false;
                break;
            }
        }
        if (wordsMatch) return true;
    }
    return false;
};