Design Add and Search Words Data Structure (medium)

Problem Statement

Design a data structure that allows you to:

  1. Add a word.
  2. Search for a word that can include dots ('.') as wildcards, where the dot represents any single character.

In simpler words, this data structure should support two operations: adding a whole word and searching for a word (with or without wildcards).

Examples

Example 1:

  • Input:
    ["Solution", "addWord", "addWord", "search", "search"]
    [[], ["apple"], ["banana"], ["apple"], ["....."]]
    
  • Expected Output:
    [-1, -1, -1, 1, 1]
    
  • Justification: After adding the words "apple" and "banana", searching for "apple" will return true since "apple" is in the data structure. Searching for "....." will also return true as both "apple" and "banana" match the pattern.

Example 2:

  • Input:
    ["Solution", "addWord", "addWord", "search", "search"]
    [[], ["cat"], ["dog"], ["c.t"], ["d..g"]]
    
  • Expected Output:
    [-1, -1, -1, 1, 0]
    
  • Justification: "c.t" matches "cat" and "d..g" doesn't matches "dog".

Example 3:

  • Input:
    ["Solution", "addWord", "search", "search"]
    [[], ["hello"], ["h.llo"], ["h...o"]]
    
  • Expected Output:
    [-1, -1, 1, 0]
    
  • Justification: "h.llo" and "h...o" both match "hello".

Try it yourself

Try solving this question here:

Python3
Python3

. . .