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

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.

Rust Solution

Rust's HashMap<char, TrieNode> keys on Unicode char, so add_word walks with word.chars() and folds the check-then-insert into a single lookup via entry(c).or_insert_with(TrieNode::new); reassigning the &mut self.root binding descends the trie while the borrow checker tracks one live mutable path. search runs word.chars().collect::<Vec<_>>().as_slice() up front so recursion can cheaply reslice with &word[i + 1..] rather than re-scanning UTF-8. search_in_node iterates word.iter().enumerate() and matches node.children.get(&c) on its Some(n) / None arms, falling through to node.children.values() on the wildcard branch.

Go Solution

Go's map[byte]*TrieNode keys on byte, since indexing a string with word[i] yields a byte rather than a rune, and the nodes are stored as pointers (*TrieNode) built by make. The comma-ok form n, ok := node.children[c] (and _, ok := node.children[c] in AddWord) does the presence check and fetch in one map access. Rather than reslice the string like the Rust version, searchInNode threads an idx int and recurses with i+1, avoiding per-call substring allocations, while the wildcard branch fans out over for _, child := range node.children.