Design Add and Search Words Data Structure — Step-by-Step Visualization
mediumLeetCode #211StringDepth-First SearchDesignTrie
Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the `WordDictionary` class: `WordDictionary()`, `addWord(word)`, `search(word)`. `word` may contain dots '.' where dots can be matched with any letter.
Algorithm Pattern
Trie with Recursive Backtracking
Key Idea
This is an extension of the standard Trie (Prefix Tree). For standard character matching, we follow the corresponding child node. For the '.' wildcard, we must perform a Depth-First Search (DFS) by checking all existing children at the current level. If any of those branches match the remainder of the word, we return `True`.
Step-by-Step Approach
- Define `TrieNode` with `children = {}` and `isEndOfWord = False`.
- AddWord(word): standard Trie insertion.
- Search(word): Recursive DFS function `searchInNode(word, node)`.
- If `word` empty, return `node.isEndOfWord`.
- If `word[0] == '.'`, recursively call `searchInNode(word[1:], child)` for EVERY child in `node.children`.
- Else, if `word[0]` in `node.children`, call `searchInNode(word[1:], node.children[word[0]])`.
- Return `True` if any branch returns `True`, else `False`.
Common Gotchas
- The '.' wildcard requires a full search of all possible branches at that depth, which can be computationally expensive if there are many wildcards.