Implement Trie with Wildcard Search in JavaScript

This challenge focuses on building a Trie data structure that supports wildcard characters in search queries. Tries are efficient for prefix-based searching, and extending them to handle wildcards allows for more flexible pattern matching, useful in applications like autocomplete, spell checkers, and searching through dictionaries.

Problem Description

You need to implement a Trie data structure in JavaScript that can store a collection of words. The Trie should support two primary operations:

insert(word): Adds a word to the Trie.
search(word): Checks if a given word exists in the Trie. This search function must support a wildcard character, specifically the dot (.), which can match any single character.

Key Requirements:

The Trie should be implemented using a class or a factory function.
Each node in the Trie should represent a character.
A node should have a way to store its children (e.g., a map or an object).
A node should indicate if it marks the end of a valid word.
The search function should correctly handle the wildcard character (.).

Expected Behavior:

insert(word): After inserting a word, subsequent searches for that exact word should return true.
search(word):
- If the word contains no wildcards, it should behave like a standard Trie search.
- If the word contains one or more wildcards, each wildcard (.) should match any single character at that position.
- If the word matches a path in the Trie and ends at a node marking the end of a word, return true.
- If no such match is found, return false.

Edge Cases to Consider:

Empty Trie: Searching an empty Trie should always return false.
Empty Word: Inserting an empty word might need specific handling (e.g., not allowed or represented by a special marker). For this challenge, assume words are non-empty strings of lowercase alphabetic characters.
Wildcard at the beginning, middle, or end of the search term.
Multiple consecutive wildcards.
Searching for a word that is a prefix of an inserted word, but not a full word itself.
Searching for a word where a prefix exists, but the full word doesn't.

Examples

Example 1:

Input:
let trie = new Trie();
trie.insert("apple");
trie.insert("apricot");
trie.insert("banana");

console.log(trie.search("apple"));    // Output: true
console.log(trie.search("app"));      // Output: false (app is a prefix, but not a full word)
console.log(trie.search("apricot"));  // Output: true
console.log(trie.search("ban"));      // Output: false
console.log(trie.search("banana"));   // Output: true

Explanation: The Trie is populated with "apple", "apricot", and "banana". Searches for exact matches return true, while searches for prefixes that aren't complete words return false.

Example 2:

Input:
let trie = new Trie();
trie.insert("apple");
trie.insert("apricot");
trie.insert("banana");
trie.insert("bat");

console.log(trie.search("ap.le"));    // Output: true ('.' matches 'p')
console.log(trie.search("ap.le"));    // Output: true ('.' matches 'p')
console.log(trie.search("b.t"));      // Output: true ('.' matches 'a' for "bat")
console.log(trie.search("b.n"));      // Output: false (no word like 'b' followed by any char and then 'n' exists as a full word)
console.log(trie.search("app.e"));    // Output: true ('.' matches 'l')
console.log(trie.search("a.r.c.t"));  // Output: true ('.' matches 'p', 'i', 'c')
console.log(trie.search("......"));   // Output: false (no 6-letter word exists in this trie)

Explanation: The wildcard searches demonstrate the flexibility. "ap.le" matches "apple", "b.t" matches "bat", and "a.r.c.t" matches "apricot". Searches that don't find a valid word ending after matching the pattern return false.

Example 3: Edge Case with Wildcards

Input:
let trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("card");

console.log(trie.search(".at"));      // Output: true (matches "cat")
console.log(trie.search("c.r"));      // Output: true (matches "car")
console.log(trie.search("c.r."));     // Output: true (matches "card")
console.log(trie.search("c.."));      // Output: true (matches "cat" and "car")
console.log(trie.search("c..."));     // Output: true (matches "card")
console.log(trie.search("..."));      // Output: true (matches "cat", "car")
console.log(trie.search("...."));     // Output: true (matches "card")
console.log(trie.search("c."));       // Output: false (no 2-letter word starting with 'c' exists)
console.log(trie.search("c.d"));      // Output: false (no word matches this pattern)

Explanation: This example highlights how multiple paths can be explored with wildcards and how the search must backtrack or explore different branches. "c.." can match both "cat" and "car" if they exist, but the search function should return true as long as at least one valid word is found.

Constraints

Words inserted will consist of lowercase English letters ('a'-'z').
The search term can contain lowercase English letters ('a'-'z') and the wildcard character ('.').
The length of any word and search term will be between 1 and 100 characters, inclusive.
The total number of words inserted into the Trie will not exceed 10,000.
The insert and search operations should be reasonably efficient. Aim for time complexity related to the length of the words/search terms, ideally O(L) for insert and O(L) in the best case for search (no wildcards) and O(L*26) or O(L^2) in the worst case for search with wildcards, where L is the length of the word/search term.

Notes

Consider using a JavaScript Map or a plain object for the children property of each Trie node. This allows for easy mapping of characters to child nodes.
A boolean flag on each node can indicate if that node represents the end of a complete word.
The wildcard search (.) will likely require a recursive approach or a depth-first search (DFS) strategy to explore all possible paths. You'll need to handle the branching logic when a wildcard is encountered.
Think about how to pass the current index and the current node to your recursive search function.