List all words in a dictionary that start with <user input>

Question

How would a go about making a program where the user enters a string, and the program generates a list of words beginning with that string?

Ex:
User: "abd"
Program:abdicate, abdomen, abduct...

Thanks!

---

Edit: I'm using python, but I assume that this is a fairly language-independent problem.

Answer 1

Use a trie.

Add your list of words to a trie. Each path from the root to a leaf is a valid word. A path from a root to an intermediate node represents a prefix, and the children of the intermediate node are valid completions for the prefix.

Answer 2

One of the best ways to do this is to use a directed graph to store your dictionary. It takes a little bit of setting up, but once done it is fairly easy to then do the type of searches you are talking about.

The nodes in the graph correspond to a letter in your word, so each node will have one incoming link and up to 26 (in English) outgoing links.

You could also use a hybrid approach where you maintain a sorted list containing your dictionary and use the directed graph as an index into your dictionary. Then you just look up your prefix in your directed graph and then go to that point in your dictionary and spit out all words matching your search criteria.