Wildcard Trie Implementation in JavaScript

This challenge asks you to implement a Trie data structure in JavaScript that supports wildcard searches. Tries (also known as prefix trees) are efficient for storing and retrieving strings based on their prefixes. Adding wildcard support allows for more flexible searching, enabling you to find words that match a pattern with unknown characters.

Problem Description

You are to implement a WildcardTrie class in JavaScript. This class should provide the following functionalities:

• insert(word): Inserts a word into the Trie. The word can contain lowercase English letters ('a' - 'z').
• search(word): Searches for a word in the Trie. The word can contain lowercase English letters ('a' - 'z') and wildcard characters ('?'). A '?' wildcard matches any single character. The search should be case-sensitive.
• startsWith(prefix): Checks if there is any word in the Trie that starts with the given prefix. The prefix can contain lowercase English letters ('a' - 'z') and wildcard characters ('?'). A '?' wildcard matches any single character. The search should be case-sensitive.

The Trie should be implemented using nested JavaScript objects to represent the nodes. Each node should store a boolean value indicating whether it represents the end of a valid word and a map of child nodes, where keys are characters (or '?' for wildcards) and values are the corresponding child nodes.

Expected Behavior:

• The Trie should be initially empty.
• insert() should add the word to the Trie.
• search() should return true if the word exists in the Trie, and false otherwise.
• startsWith() should return true if any word in the Trie starts with the given prefix, and false otherwise.

Edge Cases to Consider:

• Empty word/prefix.
• Words/prefixes containing only wildcards.
• Words/prefixes that are prefixes of other words.
• Duplicate words.
• Large number of words in the Trie.

Examples

Example 1:

Input:
insert("apple")
insert("banana")
search("apple")
Output: true
Explanation: "apple" is present in the Trie.

Example 2:

Input:
insert("apple")
insert("banana")
search("app?")
Output: true
Explanation: "app?" matches "apple".

Example 3:

Input:
insert("apple")
insert("banana")
search("bana?")
Output: true
Explanation: "bana?" matches "banana".

Example 4:

Input:
insert("apple")
insert("banana")
search("orange")
Output: false
Explanation: "orange" is not present in the Trie.

Example 5:

Input:
insert("apple")
insert("banana")
startsWith("app")
Output: true
Explanation: "apple" starts with "app".

Example 6:

Input:
insert("apple")
insert("banana")
startsWith("ap?")
Output: true
Explanation: "apple" starts with "ap?".

Example 7:

Input:
insert("apple")
insert("banana")
startsWith("oran")
Output: false
Explanation: No word starts with "oran".

Constraints

• The words and prefixes will contain only lowercase English letters ('a' - 'z') and the wildcard character '?'.
• The maximum length of a word or prefix will be 100.
• The number of words that will be inserted into the Trie will be at most 1000.
• The time complexity of insert(), search(), and startsWith() should be, on average, proportional to the length of the word/prefix.

Notes

• Consider using recursion or iteration to traverse the Trie.
• Think about how to handle the wildcard character during the search and startsWith operations.
• Pay attention to the base cases in your recursive functions.
• A good approach is to build the Trie node by node as you insert words.
• The startsWith function should return true if any word in the trie starts with the prefix, not just if the prefix itself is a word in the trie.