Solving Design Add and Search Words Data Structure: Implementing an Advanced Trie

The "Design Add and Search Words Data Structure" problem involves developing a data structure that not only stores a collection of strings but also supports searching with wildcard characters.

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string. The search method should be able to handle wildcard characters, where a . character can represent any letter.

Example of Functionality

• Add Word: Add words like "bad", "dad", and "mad" to the data structure.
• Search: Perform searches like ".ad" (matches "bad", "dad", "mad"), "b.." (matches "bad").

Solution Approach - Trie with Backtracking

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

  constructor() {
    this.children = new Map();
    this.isEndOfWord = 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.isEndOfWord = true;
  }

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

  private searchInNode(word: string, node: TrieNode): boolean {
    for (let i = 0; i < word.length; i++) {
      const char = word.charAt(i);
      if (!node.children.has(char)) {
        if (char === ".") {
          for (const [_, childNode] of node.children) {
            if (this.searchInNode(word.substring(i + 1), childNode)) {
              return true;
            }
          }
        }
        return false;
      } else {
        node = node.children.get(char)!;
      }
    }
    return node.isEndOfWord;
  }
}

Breaking Down the Solution

• Trie Structure: The core of this data structure is a Trie to store the words efficiently.
• Wildcard Handling: The search method incorporates backtracking to handle wildcards ('.') by exploring all possible paths.
• Recursive Search: A helper function searchInNode is used for recursive searching with wildcard support.

Conclusion

Designing a word dictionary with add and search functionalities, especially handling wildcard searches, is an engaging exercise in Trie data structures and backtracking algorithms.