Prefix and Suffix Search

Hard · Trie · about 30 minutes

Asked at Google, Meta, Amazon.

Design a dictionary that finds words by prefix and suffix.

• WordFilter(words) stores the words (index i is words[i]).
• f(pref, suff) returns the largest index of a word that starts with pref and ends with suff, or -1

if there is none.

Related guides

• Trie