DSA_Problems/CodeStudio/ImplementTrieII.cpp at main · lakshitcodes/DSA_Problems · GitHub

History

177 lines (162 loc) · 5.02 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

#include <bits/stdc++.h>

using namespace std;

// Question Link : https://www.naukri.com/code360/problems/implement-trie_1387095

// 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();

}

};

DSA_Problems/CodeStudio/ImplementTrieII.cpp at main · lakshitcodes/DSA_Problems · GitHub

Expand file tree

Breadcrumbs

ImplementTrieII.cpp

Latest commit

History

Breadcrumbs

ImplementTrieII.cpp

File metadata and controls