Autocomplete

Goal

Imagine you're typing on your phone, and as you start typing a word, suggestions pop up to help you finish it. This is about building a smart suggestion tool that accomplishes just that.

Overall, the goal is to make typing easier and faster by predicting what you want to write based on what you've typed before.

How It's Accomplished

Idea: When you type the beginning of a word (like "sh"), the tool looks for words that start with those letters and gives you a list of options (like "she," "ship," "shell").

Learning: If you pick one of the suggestions (for example, "ship"), the next time you type "sh," "ship" should show up at the top of the list because you chose it before.

Organization: The suggestions are neatly organized, with shorter words appearing first. If two words are the same length, then they are sorted alphabetically.

Techniques Used

Data Structure: Trie is a type of tree that helps store words efficiently. Each node in the trie represents a letter, and paths through the tree spell out complete words. This structure allows quick searches for prefixes (like "sh") to find matching words.

Finding and Organizing Candidate Words: When you enter a prefix, the program looks through the trie to find all words that start with that prefix. This is done by recursively exploring the nodes in the trie that follow the prefix, collecting words as it goes.

After finding all the potential words, the code sorts these suggestions based on two criteria: length and alphabetical order.

Storing and Managing Candidate Words: I used ArrayLists for flexible storage of candidate words and Hashtables for quick access to the words associated with each prefix, allowing for efficient updates and retrievals. There are no duplicates that appear and it only shows a limited number of suggestions (as specified by the user).

Sample Input & Output