Tries

Prefix Tree or Tries solve "StartsWith" function problem ( o(1) run time) - other functionalities can be solved using HashMap or HashSet.