Autocomplete System Using Trie in Java

An autocomplete system predicts the completion of a word being typed by the user. A Trie (prefix tree) is an efficient data structure for implementing such a system because it allows quick lookups, insertions, and prefix-based searches.

Program Structure

The autocomplete system implementation consists of three main classes:

• TrieNode: Represents a single node in the Trie.
• Trie: Manages the Trie structure, allowing insertion, search, and prefix matching operations.
• AutocompleteSystem: Provides the interface to interact with the Trie and retrieve autocomplete suggestions based on a given prefix.

1. TrieNode Class

This class represents a node in the Trie. Each node contains:

• An array of TrieNode references for its children (one for each letter of the alphabet).
• A boolean flag isEndOfWord that marks whether the node represents the end of a word.

2. Trie Class

This class manages the Trie, providing methods to insert words and search for them, as well as to find all words with a given prefix. The main methods are:

• insert(String word): Inserts a word into the Trie.
• search(String word): Searches for a word in the Trie and returns true if it exists.
• startsWith(String prefix): Returns a list of all words in the Trie that start with the given prefix.

3. AutocompleteSystem Class

This class provides the main interface for the autocomplete system. It interacts with the Trie to provide autocomplete suggestions. The main methods are:

• AutocompleteSystem(List<String> words): Initializes the Trie with a list of words.
• getSuggestions(String prefix): Returns a list of autocomplete suggestions based on the given prefix.

Java Code Implementation

TrieNode Class


public class TrieNode {
private TrieNode[] children;
private boolean isEndOfWord;

public TrieNode() {
children = new TrieNode[26]; // Assuming only lowercase a-z letters
isEndOfWord = false;
}

public TrieNode getChild(char ch) {
return children[ch – ‘a’];
}

public void setChild(char ch, TrieNode node) {
children[ch – ‘a’] = node;
}

public boolean isEndOfWord() {
return isEndOfWord;
}

public void setEndOfWord(boolean endOfWord) {
isEndOfWord = endOfWord;
}
}

Trie Class


import java.util.ArrayList;
import java.util.List;

public class Trie {
private TrieNode root;

public Trie() {
root = new TrieNode();
}

public void insert(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (current.getChild(ch) == null) {
current.setChild(ch, new TrieNode());
}
current = current.getChild(ch);
}
current.setEndOfWord(true);
}

public List<String> getWordsWithPrefix(String prefix) {
List<String> results = new ArrayList<>();
TrieNode current = root;
for (char ch : prefix.toCharArray()) {
current = current.getChild(ch);
if (current == null) {
return results;
}
}
findAllWords(current, prefix, results);
return results;
}

private void findAllWords(TrieNode node, String prefix, List<String> results) {
if (node.isEndOfWord()) {
results.add(prefix);
}
for (char ch = ‘a’; ch <= ‘z’; ch++) {
TrieNode child = node.getChild(ch);
if (child != null) {
findAllWords(child, prefix + ch, results);
}
}
}
}

AutocompleteSystem Class


import java.util.List;

public class AutocompleteSystem {
private Trie trie;

public AutocompleteSystem(List<String> words) {
trie = new Trie();
for (String word : words) {
trie.insert(word);
}
}

public List<String> getSuggestions(String prefix) {
return trie.getWordsWithPrefix(prefix);
}
}

Conclusion

This Java implementation of an autocomplete system using a Trie is both efficient and straightforward. The Trie structure allows for fast lookups and prefix-based searches, making it an ideal choice for implementing features like autocomplete. The AutocompleteSystem class provides a simple interface to interact with the Trie and retrieve suggestions based on user input.