123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209
#include <bits/stdc++.h>
using namespace std;
/* Define a struct for
each node in the trie */
struct Node {
/* Array to store
links to child nodes */
Node* links[26];
/* Counter for number of
words that end at this node */
int cntEndWith = 0;
/* Counter for number of words
that have this node as a prefix */
int cntPrefix = 0;
/* Function to check if the
node contains a specific key */
bool containsKey(char ch) {
/* Check if the link corresponding
to the character exists */
return (links[ch - 'a'] != NULL);
}
/* Function to get the child
node corresponding to a key */
Node* get(char ch) {
/* Return the link
corresponding to the character */
return links[ch - 'a'];
}
/* Function to insert a child
node with a specific key */
void put(char ch, Node* node) {
/* Set the link corresponding to
the character to the provided node */
links[ch - 'a'] = node;
}
/* Function to increment the
count of words that end at this node */
void increaseEnd() {
/* Increment the counter */
cntEndWith++;
}
/* Function to increment the count of
words that have this node as a prefix */
void increasePrefix() {
/* Increment the counter */
cntPrefix++;
}
/* Function to decrement the count
of words that end at this node */
void deleteEnd() {
/* Decrement the counter */
cntEndWith--;
}
/* Function to decrement the count of
words that have this node as a prefix */
void reducePrefix() {
/* Decrement the counter */
cntPrefix--;
}
};
/* Define a class for the
trie data structure */
class Trie {
private:
/* Pointer to the
root node of the trie */
Node* root;
public:
/* Constructor to initialize
the trie with an empty root node */
Trie() {
/* Create a new root node */
root = new Node();
}
/* Function to insert
a word into the trie */
void insert(string word) {
/* Start from the root node */
Node* node = root;
/* Iterate over each
character in the word */
for (int i = 0; i < word.size(); i++) {
/* If the character is
not already in the trie */
if (!node->containsKey(word[i])) {
/* Create a new node
for the character */
node->put(word[i], new Node());
}
/* Move to the child node
corresponding to the character */
node = node->get(word[i]);
/* Increment the prefix
count for the node */
node->increasePrefix();
}
/* Increment the end count
for the last node of the word */
node->increaseEnd();
}
/* Function to count the number
of words equal to a given word */
int countWordsEqualTo(string word) {
/* Start from the root node */
Node* node = root;
/* Iterate over each character in the word */
for (int i = 0; i < word.size(); i++) {
/* If the character is found in the trie */
if (node->containsKey(word[i])) {
/* Move to the child node
corresponding to the character */
node = node->get(word[i]);
} else {
/* Return 0 if the
character is not found */
return 0;
}
}
/* Return the count of
words ending at the node */
return node->cntEndWith;
}
/* Function to count the number of
words starting with a given prefix */
int countWordsStartingWith(string word) {
/* Start from the root node */
Node* node = root;
/* Iterate over each character in the prefix */
for (int i = 0; i < word.size(); i++) {
/* If the character is found in the trie */
if (node->containsKey(word[i])) {
/* Move to the child node
corresponding to the character */
node = node->get(word[i]);
} else {
/* Return 0 if the
character is not found */
return 0;
}
}
/* Return the count of
words with the prefix */
return node->cntPrefix;
}
/* Function to erase a
word from the trie */
void erase(string word) {
/* Start from the root node */
Node* node = root;
/* Iterate over each
character in the word */
for (int i = 0; i < word.size(); i++) {
/* If the character is
found in the trie */
if (node->containsKey(word[i])) {
/* Move to the child node
corresponding to the character */
node = node->get(word[i]);
/* Decrement the prefix
count for the node */
node->reducePrefix();
} else {
/* Return if the
character is not found */
return;
}
}
/* Decrement the end count
for the last node of the word */
node->deleteEnd();
}
};
int main() {
Trie trie;
trie.insert("apple");
trie.insert("apple");
cout << "Inserting strings 'apple' twice into Trie" << endl;
cout << "Count Words Equal to 'apple': ";
cout << trie.countWordsEqualTo("apple") << endl;
cout << "Count Words Starting With 'app': ";
cout << trie.countWordsStartingWith("app") << endl;
cout << "Erasing word 'apple' from trie" << endl;
trie.erase("apple");
cout << "Count Words Equal to 'apple': ";
cout << trie.countWordsEqualTo("apple") << endl;
cout << "Count Words Starting With 'app': ";
cout << trie.countWordsStartingWith("app") << endl;
cout << "Erasing word 'apple' from trie" << endl;
trie.erase("apple");
cout << "Count Words Starting With 'app': ";
cout << trie.countWordsStartingWith("app") << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202
import java.util.*;
class Node {
/* Array to store links to child nodes,
each index represents a letter */
private Node[] links;
/* Counter for number of words
that end at this node */
private int cntEndWith;
/* Counter for number of words
that have this node as a prefix */
private int cntPrefix;
// Constructor
public Node() {
links = new Node[26];
cntEndWith = 0;
cntPrefix = 0;
}
/* Check if the node contains
a specific key (letter) */
public boolean containsKey(char ch) {
/* Check if the link corresponding
to the character exists */
return links[ch - 'a'] != null;
}
/* Get the node with a specific
key (letter) from the Trie */
public Node get(char ch) {
/* Return the link
corresponding to the character */
return links[ch - 'a'];
}
/* Insert a new node with a specific
key (letter) into the Trie */
public void put(char ch, Node node) {
/* Set the link corresponding to
the character to the provided node */
links[ch - 'a'] = node;
}
/* Increment the count of words
that end at this node */
public void increaseEnd() {
/* Increment the counter */
cntEndWith++;
}
/* Increment the count of words
that have this node as a prefix */
public void increasePrefix() {
/* Increment the counter */
cntPrefix++;
}
/* Decrement the count of words
that end at this node */
public void deleteEnd() {
/* Decrement the counter */
cntEndWith--;
}
/* Decrement the count of words
that have this node as a prefix */
public void reducePrefix() {
/* Decrement the counter */
cntPrefix--;
}
public int getEnd() {
return cntEndWith;
}
public int getPrefix() {
return cntPrefix;
}
}
// Trie class
class Trie {
private Node root;
/* Constructor to initialize the
Trie with an empty root node */
public Trie() {
root = new Node();
}
/* Inserts a word into the Trie
Time Complexity O(len), where len
is the length of the word */
public void insert(String word) {
/* Start from the root node */
Node node = root;
/* Iterate over each
character in the word */
for (int i = 0; i < word.length(); i++) {
if (!node.containsKey(word.charAt(i))) {
/* Create a new node
for the character */
node.put(word.charAt(i), new Node());
}
/* Move to the child node
corresponding to the character */
node = node.get(word.charAt(i));
/* Increment the prefix
count for the node */
node.increasePrefix();
}
/* Increment the end count
for the last node of the word */
node.increaseEnd();
}
/* Returns the number of words
equal to a given word */
public int countWordsEqualTo(String word) {
/* Start from the root node */
Node node = root;
/* Iterate over each character in the word */
for (int i = 0; i < word.length(); i++) {
if (node.containsKey(word.charAt(i))) {
/* Move to the child node
corresponding to the character */
node = node.get(word.charAt(i));
} else {
/* Return 0 if the
character is not found */
return 0;
}
}
/* Return the count of
words ending at the node */
return node.getEnd();
}
/* Returns the number of words
starting with a given prefix */
public int countWordsStartingWith(String word) {
/* Start from the root node */
Node node = root;
/* Iterate over each character in the prefix */
for (int i = 0; i < word.length(); i++) {
if (node.containsKey(word.charAt(i))) {
/* Move to the child node
corresponding to the character */
node = node.get(word.charAt(i));
} else {
/* Return 0 if the
character is not found */
return 0;
}
}
/* Return the count of
words with the prefix */
return node.getPrefix();
}
/* Erases a word from the Trie */
public void erase(String word) {
/* Start from the root node */
Node node = root;
/* Iterate over each character in the word */
for (int i = 0; i < word.length(); i++) {
if (node.containsKey(word.charAt(i))) {
/* Move to the child node
corresponding to the character */
node = node.get(word.charAt(i));
/* Decrement the prefix
count for the node */
node.reducePrefix();
} else {
/* Return if the
character is not found */
return;
}
}
/* Decrement the end count
for the last node of the word */
node.deleteEnd();
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("apple");
System.out.println("Inserting strings 'apple' twice into Trie");
System.out.println("Count Words Equal to 'apple': " + trie.countWordsEqualTo("apple"));
System.out.println("Count Words Starting With 'app': " + trie.countWordsStartingWith("app"));
System.out.println("Erasing word 'apple' from Trie");
trie.erase("apple");
System.out.println("Count Words Equal to 'apple': " + trie.countWordsEqualTo("apple"));
System.out.println("Count Words Starting With 'app': " + trie.countWordsStartingWith("app"));
System.out.println("Erasing word 'apple' from Trie");
trie.erase("apple");
System.out.println("Count Words Starting With 'app': " + trie.countWordsStartingWith("app"));
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160
class Node:
def __init__(self):
# Array to store links to child nodes,
# each index represents a letter
self.links = [None] * 26
# Counter for number of words
# that end at this node
self.cntEndWith = 0
# Counter for number of words
# that have this node as a prefix
self.cntPrefix = 0
# Check if the node contains
# a specific key (letter)
def containsKey(self, ch):
# Check if the link corresponding
# to the character exists
return self.links[ord(ch) - ord('a')] is not None
# Get the node with a specific
# key (letter) from the Trie
def get(self, ch):
# Return the link
# corresponding to the character
return self.links[ord(ch) - ord('a')]
# Insert a new node with a specific
# key (letter) into the Trie
def put(self, ch, node):
# Set the link corresponding to
# the character to the provided node
self.links[ord(ch) - ord('a')] = node
# Increment the count of words
# that end at this node
def increaseEnd(self):
# Increment the counter
self.cntEndWith += 1
# Increment the count of words
# that have this node as a prefix
def increasePrefix(self):
# Increment the counter
self.cntPrefix += 1
# Decrement the count of words
# that end at this node
def deleteEnd(self):
# Decrement the counter
self.cntEndWith -= 1
# Decrement the count of words
# that have this node as a prefix
def reducePrefix(self):
# Decrement the counter
self.cntPrefix -= 1
class Trie:
def __init__(self):
# Constructor to initialize the
# Trie with an empty root node
self.root = Node()
# Inserts a word into the Trie
# Time Complexity O(len), where len
# is the length of the word
def insert(self, word):
# Start from the root node
node = self.root
# Iterate over each
# character in the word
for ch in word:
if not node.containsKey(ch):
# Create a new node
# for the character
node.put(ch, Node())
# Move to the child node
# corresponding to the character
node = node.get(ch)
# Increment the prefix
# count for the node
node.increasePrefix()
# Increment the end count
# for the last node of the word
node.increaseEnd()
# Returns the number of words
# equal to a given word
def countWordsEqualTo(self, word):
# Start from the root node
node = self.root
# Iterate over each character in the word
for ch in word:
if node.containsKey(ch):
# Move to the child node
# corresponding to the character
node = node.get(ch)
else:
# Return 0 if the
# character is not found
return 0
# Return the count of
# words ending at the node
return node.cntEndWith
# Returns the number of words
# starting with a given prefix
def countWordsStartingWith(self, word):
# Start from the root node
node = self.root
# Iterate over each character in the prefix
for ch in word:
if node.containsKey(ch):
# Move to the child node
# corresponding to the character
node = node.get(ch)
else:
# Return 0 if the
# character is not found
return 0
# Return the count of
# words with the prefix
return node.cntPrefix
# Erases a word from the Trie
def erase(self, word):
# Start from the root node
node = self.root
# Iterate over each character in the word
for ch in word:
if node.containsKey(ch):
# Move to the child node
# corresponding to the character
node = node.get(ch)
# Decrement the prefix
# count for the node
node.reducePrefix()
else:
# Return if the
# character is not found
return
# Decrement the end count
# for the last node of the word
node.deleteEnd()
# Testing the Trie class
trie = Trie()
trie.insert("apple")
trie.insert("apple")
print("Inserting strings 'apple' twice into Trie")
print("Count Words Equal to 'apple':", trie.countWordsEqualTo("apple"))
print("Count Words Starting With 'app':", trie.countWordsStartingWith("app"))
print("Erasing word 'apple' from Trie")
trie.erase("apple")
print("Count Words Equal to 'apple':", trie.countWordsEqualTo("apple"))
print("Count Words Starting With 'app':", trie.countWordsStartingWith("app"))
print("Erasing word 'apple' from Trie")
trie.erase("apple")
print("Count Words Starting With 'app':", trie.countWordsStartingWith("app"))
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
class Node {
constructor() {
/* Array to store links to child nodes,
each index represents a letter */
this.links = new Array(26).fill(null);
/* Counter for number of words
that end at this node */
this.cntEndWith = 0;
/* Counter for number of words
that have this node as a prefix */
this.cntPrefix = 0;
}
/* Check if the node contains
a specific key (letter) */
containsKey(ch) {
/* Check if the link corresponding
to the character exists */
return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] !== null;
}
/* Get the node with a specific
key (letter) from the Trie */
get(ch) {
/* Return the link
corresponding to the character */
return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)];
}
/* Insert a new node with a specific
key (letter) into the Trie */
put(ch, node) {
/* Set the link corresponding to
the character to the provided node */
this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] = node;
}
/* Increment the count of words
that end at this node */
increaseEnd() {
/* Increment the counter */
this.cntEndWith++;
}
/* Increment the count of words
that have this node as a prefix */
increasePrefix() {
/* Increment the counter */
this.cntPrefix++;
}
/* Decrement the count of words
that end at this node */
deleteEnd() {
/* Decrement the counter */
this.cntEndWith--;
}
/* Decrement the count of words
that have this node as a prefix */
reducePrefix() {
/* Decrement the counter */
this.cntPrefix--;
}
}
// Trie class
class Trie {
constructor() {
/* Constructor to initialize the
Trie with an empty root node */
this.root = new Node();
}
/* Inserts a word into the Trie
Time Complexity O(len), where len
is the length of the word */
insert(word) {
/* Start from the root node */
let node = this.root;
/* Iterate over each
character in the word */
for (let i = 0; i < word.length; i++) {
if (!node.containsKey(word[i])) {
/* Create a new node
for the character */
node.put(word[i], new Node());
}
/* Move to the child node
corresponding to the character */
node = node.get(word[i]);
/* Increment the prefix
count for the node */
node.increasePrefix();
}
/* Increment the end count
for the last node of the word */
node.increaseEnd();
}
/* Returns the number of words
equal to a given word */
countWordsEqualTo(word) {
/* Start from the root node */
let node = this.root;
/* Iterate over each character in the word */
for (let i = 0; i < word.length; i++) {
if (node.containsKey(word[i])) {
/* Move to the child node
corresponding to the character */
node = node.get(word[i]);
} else {
/* Return 0 if the
character is not found */
return 0;
}
}
/* Return the count of
words ending at the node */
return node.cntEndWith;
}
/* Returns the number of words
starting with a given prefix */
countWordsStartingWith(word) {
/* Start from the root node */
let node = this.root;
/* Iterate over each character in the prefix */
for (let i = 0; i < word.length; i++) {
if (node.containsKey(word[i])) {
/* Move to the child node
corresponding to the character */
node = node.get(word[i]);
} else {
/* Return 0 if the
character is not found */
return 0;
}
}
/* Return the count of
words with the prefix */
return node.cntPrefix;
}
/* Erases a word from the Trie */
erase(word) {
/* Start from the root node */
let node = this.root;
/* Iterate over each character in the word */
for (let i = 0; i < word.length; i++) {
if (node.containsKey(word[i])) {
/* Move to the child node
corresponding to the character */
node = node.get(word[i]);
/* Decrement the prefix
count for the node */
node.reducePrefix();
} else {
/* Return if the
character is not found */
return;
}
}
/* Decrement the end count
for the last node of the word */
node.deleteEnd();
}
}
// Testing the Trie class
const trie = new Trie();
trie.insert("apple");
trie.insert("apple");
console.log("Inserting strings 'apple' twice into Trie");
console.log("Count Words Equal to 'apple':", trie.countWordsEqualTo("apple"));
console.log("Count Words Starting With 'app':", trie.countWordsStartingWith("app"));
console.log("Erasing word 'apple' from Trie");
trie.erase("apple");
console.log("Count Words Equal to 'apple':", trie.countWordsEqualTo("apple"));
console.log("Count Words Starting With 'app':", trie.countWordsStartingWith("app"));
console.log("Erasing word 'apple' from Trie");
trie.erase("apple");
console.log("Count Words Starting With 'app':", trie.countWordsStartingWith("app"));
