Got ask this question today, anyone knows how to solve it? I tried to come up with a recursive function in search() method which search for all possible combination. Then search each one in the hash map. I failed as I am not able to write the correct recursive function...

Design a data structure with add() and search() method:

1. add(word)
   add a "word" into the data structure, this function doesn't need to return anything
   e.g.

   • add("abc")
   • add("def")
   • add("ghi")
   • add("ab")

2. search(word):

• word: string type
• this function returns a boolean value which indicate whether "word" exists in the data structure
  e.g:
  • search("abc") --> True
  • search("xyz") --> False
  • search("?bc") --> True