> Since the problem does not concern itself with prefixes, there is no need for a prefix tree This is a very important point, and many others in this thread ha

> Since the problem does not concern itself with prefixes, there is no need for a prefix tree This is a very important point, and many others in this thread have missed the fundamental point with using a trie. A real world example would immediately showcase its benefit. In the old feature phones, you needed to punch the number keys many times to get a letter. Some people improved this using something called predictive typing - which basically goes like this: 1. Each number can be mapped to one of 3-4 possible letters 2. Based on the current sequence of numbers typed in (i.e. the prefix up to this point), this can mean 0 or more words which are in the dictionary. 3. Using a trie data structure, you basically have a few possible leaf nodes (only dictionary words can be leaf nodes in the predictive typing scenario) which all map to the current sequence of numbers. 4. Hence you will notice one or more options from which you can select based on the number sequence you typed, thus saving you many keystrokes You can present the different options sorted by word frequency etc. if there are multiple matching leaf nodes for the given prefix. When the prefix scenario does not matter - as in OP's article, from what I remember the trie gives no benefit over a simple sorted dictionary.