Code Implementation

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

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

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

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == '.':
                return any(dfs(child, i+1) for child in node.children.values())
            if ch in node.children:
                return dfs(node.children[ch], i+1)
            return False
        return dfs(self.root, 0)
      

class TrieNode {
public:
    TrieNode* children[26];
    bool is_end;
    TrieNode() : is_end(false) {
        for (int i = 0; i < 26; ++i) children[i] = nullptr;
    }
};

class WordDictionary {
private:
    TrieNode* root;
    bool dfs(TrieNode* node, const string& word, int i) {
        if (i == word.size()) return node->is_end;
        char ch = word[i];
        if (ch == '.') {
            for (int j = 0; j < 26; ++j) {
                if (node->children[j] && dfs(node->children[j], word, i+1))
                    return true;
            }
            return false;
        } else {
            int idx = ch - 'a';
            if (!node->children[idx]) return false;
            return dfs(node->children[idx], word, i+1);
        }
    }
public:
    WordDictionary() {
        root = new TrieNode();
    }

    void addWord(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->is_end = true;
    }

    bool search(string word) {
        return dfs(root, word, 0);
    }
};
      

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

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

    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(TrieNode node, String word, int i) {
        if (i == word.length()) return node.isEnd;
        char ch = word.charAt(i);
        if (ch == '.') {
            for (TrieNode child : node.children) {
                if (child != null && dfs(child, word, i + 1)) return true;
            }
            return false;
        } else {
            int idx = ch - 'a';
            if (node.children[idx] == null) return false;
            return dfs(node.children[idx], word, i + 1);
        }
    }
}
      

class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

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

    addWord(word) {
        let node = this.root;
        for (let ch of word) {
            if (!(ch in node.children)) {
                node.children[ch] = new TrieNode();
            }
            node = node.children[ch];
        }
        node.isEnd = true;
    }

    search(word) {
        const dfs = (node, i) => {
            if (i === word.length) return node.isEnd;
            let ch = word[i];
            if (ch === '.') {
                for (let child of Object.values(node.children)) {
                    if (dfs(child, i + 1)) return true;
                }
                return false;
            } else {
                if (!(ch in node.children)) return false;
                return dfs(node.children[ch], i + 1);
            }
        }
        return dfs(this.root, 0);
    }
}
      

Problem Description

You are tasked with designing a data structure that supports adding new words and searching for words, where the search operation can include the special character '.'. The dot character '.' acts as a wildcard, matching any single letter.

• Implement a class WordDictionary with two operations:
• addWord(word): Adds a word to the data structure.
• search(word): Searches for a word in the data structure. The word can contain the '.' character, which matches any letter.
• All words consist of lowercase English letters.
• Each search must return true if any previously added word matches the search pattern, and false otherwise.
• There may be multiple calls to addWord and search in any order.

Thought Process

The problem asks us to store words and later search for them, supporting wildcard searches with '.'. At first glance, we might consider storing all words in a list or set, and for each search, iterate over all stored words and compare them character by character, treating '.' as a wildcard.

However, this brute-force approach is inefficient, especially if we have many words and frequent searches. We need a data structure that allows fast insertions and searches, especially when handling the wildcard character efficiently.

The Trie (prefix tree) data structure is well-suited for word storage and prefix-based queries. But, with the wildcard '.', we need to consider searching all possible branches at wildcard positions. This leads us to a recursive (or DFS) search strategy within the Trie.

Solution Approach

To efficiently support both adding and searching words (with wildcards), we use a Trie data structure. Here's how we design and implement it:

1. Trie Node Structure:
   • Each node has a mapping from characters to child nodes (for 26 lowercase letters).
   • A boolean flag indicates if the node marks the end of a word.
2. Adding Words:
   • Traverse the Trie, creating child nodes as needed for each character in the word.
   • After the last character, set the end-of-word flag to true.
3. Searching Words (with Wildcards):
   • For each character in the search word:
     • If the character is a letter, follow the corresponding child node.
     • If the character is '.', recursively search all child nodes at this position.
   • If we reach the end of the pattern, return true if the current node is the end of a word.
   • This recursive search ensures all possible matches for wildcards are checked.

This approach is efficient for both adding and searching words, even with wildcards, due to the Trie structure's branching and pruning capabilities.

Example Walkthrough

Let's walk through an example:

• We call addWord("bad"), addWord("dad"), and addWord("mad").
• Now, we search for "pad":
  • We traverse the Trie for 'p' - not found. Return false.
• We search for "bad":
  • We traverse for 'b' → 'a' → 'd', reach end-of-word. Return true.
• We search for ".ad":
  • First character is '.', so we try all children at root:
  • Try 'b': 'b' → 'a' → 'd' (match)
  • Try 'd': 'd' → 'a' → 'd' (match)
  • Try 'm': 'm' → 'a' → 'd' (match)
  • Any match returns true.
• We search for "b..":
  • Traverse for 'b', then try all children at each '.' position.
  • Find 'a' and then 'd' (completing "bad"). Return true.

Time and Space Complexity

• Brute-force Approach:
  • Adding: O(1) per word (using a list or set).
  • Searching: O(N * L), where N is the number of words and L is the word length, since each search may compare against every word.
• Optimized Trie Approach:
  • Adding: O(L) per word, where L is the length of the word.
  • Searching (no wildcards): O(L), since we follow one path down the Trie.
  • Searching (with wildcards): Worst case O(26^d * L), where d is the number of wildcards, since each '.' can branch to all 26 children. In practice, it's much faster due to early pruning.
  • Space: O(N * L), since each node represents a character in the stored words.

Summary

The key to solving the "Design Add and Search Words Data Structure" problem efficiently is using a Trie to store words for fast insertions and searches. The recursive search strategy allows us to handle the wildcard character '.' elegantly by exploring all possible paths in the Trie at wildcard positions. This approach is both space- and time-efficient for the problem's requirements, and showcases the power of Tries for string and pattern matching tasks.