Java - Implementing a Trie in Java
When working with strings in programming, especially in problems like autocomplete, spell checking, and word searching, an efficient data structure called a Trie becomes extremely useful.
In this blog, we'll explore what a Trie is, why you might want to use it, and how you can implement it in Java.
What is a Trie?
A Trie (pronounced try) is a tree-like data structure that stores a dynamic set of strings. It is often used for retrieval of a key in a dataset of strings. Keys are usually words, and nodes represent characters of the word.
Key points:
Each node stores a character.
A path from the root to a node represents a prefix.
Words sharing a prefix share part of the path.
For example, the words cat, cap, and can will share the first two characters ca in the Trie.
Why Use a Trie?
Fast search: Searching for a word of length L takes O(L) time.
Efficient storage: Common prefixes are stored only once.
Prefix matching: Easy to find all words starting with a given prefix.
Basic Trie Operations
The main operations we typically want in a Trie are:
Insert a word
Search for a word
Check if any word starts with a given prefix
Let's see how we can implement these in Java.
Implementing a Trie in Java
Here's a simple and clean Trie implementation:
import java.util.HashMap;
class TrieNode {
HashMap<Character, TrieNode> children;
boolean isEndOfWord;
public TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Insert a word into the Trie
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node.children.putIfAbsent(c, new TrieNode());
node = node.children.get(c);
}
node.isEndOfWord = true;
}
// Search for a word in the Trie
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.get(c);
if (node == null) {
return false;
}
}
return node.isEndOfWord;
}
// Check if any word starts with the given prefix
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
node = node.children.get(c);
if (node == null) {
return false;
}
}
return true;
}
// Example usage
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("cat");
trie.insert("cap");
trie.insert("can");
System.out.println("Search cat: " + trie.search("cat")); // true
System.out.println("Search cap: " + trie.search("cap")); // true
System.out.println("Search can: " + trie.search("can")); // true
System.out.println("Search car: " + trie.search("car")); // false
System.out.println("Starts with ca: " + trie.startsWith("ca")); // true
System.out.println("Starts with bat: " + trie.startsWith("bat")); // false
}
}
How It Works
Insertion: We traverse the Trie for each character. If the character is not already present, we create a new node.
Searching: We move through the Trie following each character. If a required character is missing, the word doesn't exist.
Prefix Checking: We follow the same path as search, but don't care if it's the end of a word — just the presence of the path matters.
