What is a Trie?
It is a
data structure looks like a tree. Usually, it stores the data and retrieves it
accordingly. It is similar to prefix tree.
Usage: prefix lookup, insert a data and fast search.
Applications: spell checking,dictionary and autocomplete.
Program implementation:
The
implementation starts with including the built-in package java.util.
Classes included in this program:
TrieNodeEg :it creates the node and its elements.
TrieEg : This develops the root node and its value. It includes
three member functions.
TrieSample:It is in main() function. it creates the object
and calls the member functions to execute to get the output.
Member variables:
Children -it is a hash map object.
isEOF – it is a Boolean value for store the EOF value.
t_root -root elements
t_node – node element
wrd – input to the member functions.
ch -character element.
‘insert()’ – add the elements to the structure.
‘search()’ -it finds an elements.
‘startWith()’ – it checks the data starts with a particular
data or not.
Program:
import java.util.*;
class TrieNodeEg {
Map<Character,
TrieNodeEg> children;
boolean isEOF;
public
TrieNodeEg() {
children = new
HashMap<>();
isEOF = false;
}
}
class TrieEg {
private TrieNodeEg
t_root;
public TrieEg() {
t_root = new
TrieNodeEg();
}
public void
insert(String wrd) {
TrieNodeEg
t_node = t_root;
for (char ch :
wrd.toCharArray()) {
t_node.children.putIfAbsent(ch, new TrieNodeEg());
t_node =
t_node.children.get(ch);
}
t_node.isEOF =
true;
}
public boolean
search(String wrd) {
TrieNodeEg
t_node = t_root;
for (char ch :
wrd.toCharArray()) {
if
(!t_node.children.containsKey(ch)) {
return
false;
}
t_node =
t_node.children.get(ch);
}
return
t_node.isEOF;
}
public boolean
startsWith(String prefix) {
TrieNodeEg
t_node = t_root;
for (char ch :
prefix.toCharArray()) {
if
(!t_node.children.containsKey(ch)) {
return
false;
}
t_node =
t_node.children.get(ch);
}
return true;
}
}
public class TrieSample {
public static void
main(String[] args) {
TrieEg trie1 =
new TrieEg();
trie1.insert("Car");
trie1.insert("Vehicle");
trie1.insert("Bus");
System.out.println(trie1.search("Car"));
System.out.println(trie1.search("Vehicle"));
System.out.println(trie1.search("Van"));
System.out.println(trie1.startsWith("Bus"));
}
}
Output:
C:\raji\blog>javac TrieSample.java
C:\raji\blog>java TrieSample
true
true
false
true
This is the way of creating Word search application using
Trie Structure in java. Hope, this code is beneficial to you. Keep coding!!!!
No comments:
Post a Comment