Trie

  • Advantages
    • Can find all words beginning with a prefix.
  • Disadvantages
    • Tries is they require a lot of extra space.
  • Complexity
    • Search time: O(M) where M is the length of the string.