Data Structures in Java Programming Problem

Autocompletion via Tries

Write a program that prompts the user for the beginning of a word and outputs all the possible words that can complete what the user typed in alphabetical order. For example, one possible user interaction would be:

$ java AutoCompleter dictionary.txt

Loading Dictonary. Standby...

Dictionary loaded!

Start typing a word and hit enter (quit! to end)

algori

Possible completions:

algorithm

algorithmic

Perform the autocompletion lookup by storing a dictionary of words in a trie. Load the dictionary when your program starts from a text file of words. Use the included Scrabble dictionary file TWL06.txt1 . Write your own MyTrie class for Strings that performs insertions, lookup and preorder toString() conversion (no deletion is necessary). At the cost of memory usage, simplify your code by storing the full word at each leaf. The lookup method should take the beginning of a word input string and return the sub-trie of words that start with the input string. Calling toString() on this sub-trie should return the desired output (i.e., put the newlines in the string conversion to create the kind of output in the above example).

TWL06.txt1 can be found on the weblink: http://www1.cs.columbia.edu/~bert/courses/3134/hw3/TWL06.txt