programming-language/TrieDataStructure.java at main · praggCode/programming-language · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
importjava.util.HashMap;

classTrieNode {
// HashMap to store children of the node (for each character)
HashMap<Character, TrieNode> children;
// Boolean flag to mark the end of a word
booleanisEndOfWord;

// Constructor
publicTrieNode() {
children = newHashMap<>();
isEndOfWord = false;
 }
}

classTrie {
privateTrieNoderoot;

// Constructor to initialize the root node
publicTrie() {
root = newTrieNode();
 }

// Method to insert a word into the Trie
publicvoidinsert(Stringword) {
TrieNodecurrent = root;
for (charc : word.toCharArray()) {
// If the character is not already in the children, add it
current.children.putIfAbsent(c, newTrieNode());
// Move to the child node
current = current.children.get(c);
 }
// Mark the end of the word
current.isEndOfWord = true;
 }

// Method to search for a word in the Trie
publicbooleansearch(Stringword) {
TrieNodecurrent = root;
for (charc : word.toCharArray()) {
// If the character is not found in the children, return false
if (!current.children.containsKey(c)) {
returnfalse;
 }
// Move to the child node
current = current.children.get(c);
 }
// Return true if it's the end of a valid word
returncurrent.isEndOfWord;
 }

// Optional: Method to check if a prefix exists in the Trie
publicbooleanstartsWith(Stringprefix) {
TrieNodecurrent = root;
for (charc : prefix.toCharArray()) {
if (!current.children.containsKey(c)) {
returnfalse;
 }
current = current.children.get(c);
 }
returntrue;
 }
}

publicclassTrieExample {
publicstaticvoidmain(String[] args) {
Trietrie = newTrie();

// Insert words into the Trie
trie.insert("apple");
trie.insert("app");

// Search for words
System.out.println(trie.search("apple")); // Output: true
System.out.println(trie.search("app")); // Output: true
System.out.println(trie.search("appl")); // Output: false
System.out.println(trie.search("banana")); // Output: false

// Check for prefixes
System.out.println(trie.startsWith("app")); // Output: true
System.out.println(trie.startsWith("ban")); // Output: false
 }
}