A practical use case of tries is autocomplete functionality. Tries provide an efficient way to implement autocomplete or suggestion features in text editors or search engines.
In an autocomplete system, given a prefix entered by the user, the system needs to suggest a list of words that match that prefix. For example, if the user types "app", the system should suggest words like "apple" and "application".
Tries are well-suited for this task because they can efficiently find all words that match a given prefix. Starting from the root node, we can navigate through the trie following the characters in the prefix. If we reach a node where the characters don't match, we can immediately stop the traversal and return an empty list of suggestions. If we reach the end of the prefix, we can use a depth-first search to find all words below that node, which provides us with the autocomplete suggestions.
Here's an example implementation of an autocomplete class using a trie in Java:
1import java.util.ArrayList;
2import java.util.List;
3
4public class Autocomplete {
5
6 private TrieNode root;
7
8 public Autocomplete() {
9 root = new TrieNode();
10 }
11
12 // Insert a word into the trie
13 public void insert(String word) {
14 TrieNode current = root;
15
16 for (char c : word.toCharArray()) {
17 int index = c - 'a';
18 if (current.children[index] == null) {
19 current.children[index] = new TrieNode();
20 }
21 current = current.children[index];
22 }
23
24 current.isWord = true;
25 }
26
27 // Get autocomplete suggestions for a given prefix
28 public List<String> autocomplete(String prefix) {
29 TrieNode current = root;
30 List<String> suggestions = new ArrayList<>();
31
32 for (char c : prefix.toCharArray()) {
33 int index = c - 'a';
34 if (current.children[index] == null) {
35 return suggestions;
36 }
37 current = current.children[index];
38 }
39
40 autocompleteHelper(prefix, current, suggestions);
41
42 return suggestions;
43 }
44
45 private void autocompleteHelper(String prefix, TrieNode node, List<String> suggestions) {
46 if (node.isWord) {
47 suggestions.add(prefix);
48 }
49
50 for (char c = 'a'; c <= 'z'; c++) {
51 int index = c - 'a';
52 if (node.children[index] != null) {
53 autocompleteHelper(prefix + c, node.children[index], suggestions);
54 }
55 }
56 }
57
58 private class TrieNode {
59 TrieNode[] children;
60 boolean isWord;
61
62 public TrieNode() {
63 this.children = new TrieNode[26];
64 this.isWord = false;
65 }
66 }
67
68 public static void main(String[] args) {
69 Autocomplete autocomplete = new Autocomplete();
70 autocomplete.insert("apple");
71 autocomplete.insert("application");
72 autocomplete.insert("banana");
73
74 List<String> suggestions = autocomplete.autocomplete("app");
75 System.out.println(suggestions); // Output: [apple, application]
76 }
77}xxxxxxxxxx}```javaimport java.util.ArrayList;import java.util.List;public class Autocomplete { private TrieNode root; public Autocomplete() { root = new TrieNode(); } // Insert a word into the trie public void insert(String word) { TrieNode current = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (current.children[index] == null) { current.children[index] = new TrieNode(); } current = current.children[index]; } current.isWord = true; } // Get autocomplete suggestions for a given prefix public List<String> autocomplete(String prefix) {