Insert and Search Words with Wildcards

Design a data structure that efficiently stores words and supports searching for words with wildcard characters. This problem tests your understanding of tries and recursive searching, crucial for applications like autocomplete and spellcheck.

trierecursionstringdata structuresearch

Problem Statement

Implement a custom data structure that enables the insertion of words and the searching of words. The search functionality must support the use of a special wildcard character, denoted by '#', which can match any single lowercase English letter. The data structure should support two primary operations: adding a word and searching for a word (potentially containing wildcards).

Example 1

Input: insert('apple'), insert('apricot'), search('app#e')

Output: True

The word 'apple' is present, and 'app#e' can match 'apple' because '#' can be 'l'.

Example 2

Input: insert('banana'), insert('band'), search('b#n#n#')

Output: True

The word 'banana' is present, and 'b#n#n#' can match 'banana' because each '#' can be 'a'.

Constraints

-All words will consist of lowercase English letters and the '#' character.
-The length of each word will be between 1 and 20 characters.
-The number of insert and search operations will not exceed 500.
-The wildcard character '#' will only represent a single character.

Brute Force Approach

A brute-force approach would involve storing all inserted words in a list and, for each search query, iterating through the list and comparing each stored word with the query. For wildcard matches, you'd need to check every possible character substitution. This is like manually searching through a phone book, comparing each name one by one. This is inefficient.

TimeO(N*M)

SpaceO(N)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem