Problem Statement
Which of the following data structures is best for searching words in dictionaries?
Explanation
A Trie, also called a prefix tree, is the best data structure for dictionary word searches because it provides efficient prefix-based searching and storage. Each node represents a character, and paths from root to nodes represent words.
Tries excel at prefix matching with time complexity O of m where m is the word length, independent of dictionary size. They enable autocomplete features efficiently, support prefix-based searches like finding all words starting with given letters, and can store additional information like word frequency. While tries use more memory than hash tables, they are unbeatable for applications requiring prefix operations.
Code Solution
SolutionRead Only
// Trie Node Structure
class TrieNode {
TrieNode[] children = new TrieNode[26]; // For a-z
boolean isEndOfWord;
}
// Trie for words: "cat", "car", "dog"
// root
// / \
// c d
// | |
// a o
// / \ |
// t r g*
// * *
// * marks end of word
// Search "cat" - O(3) time
// Prefix search "ca" - finds "cat" and "car"
boolean search(TrieNode root, String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null)
return false;
node = node.children[c - 'a'];
}
return node.isEndOfWord;
}Practice Sets
This question appears in the following practice sets:
