Welcome to Day 29 of my 100 Days of DSA challenge! Today’s focus was on Tries, a versatile and efficient data structure for managing strings. I explored their implementation and tackled problems involving prefix searches, dictionary operations, and autocomplete systems.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Take a look the challenges solved and the techniques applied! 🚀
1. Implement a Trie
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define ALPHABET_SIZE 26
// Trie Node Structure
struct TrieNode {
TrieNode* children[ALPHABET_SIZE];
bool is_end_of_word;
TrieNode() {
is_end_of_word = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
children[i] = nullptr;
}
}
};
// Trie Class
class Trie {
private:
TrieNode* root;
// Helper function for delete operation
bool deleteHelper(TrieNode* node, const char* key, int depth, int len) {
if (!node) return false;
if (depth == len) {
if (node->is_end_of_word) {
node->is_end_of_word = false; // Unmark end of word
return isEmpty(node); // Return true if node can be deleted
}
return false;
}
int index = key[depth] - 'a';
if (deleteHelper(node->children[index], key, depth + 1, len)) {
delete node->children[index];
node->children[index] = nullptr;
return !node->is_end_of_word && isEmpty(node); // Delete if not a prefix
}
return false;
}
// Check if a node is empty
bool isEmpty(TrieNode* node) {
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (node->children[i]) return false;
}
return true;
}
public:
Trie() {
root = new TrieNode();
}
// Insert a word into the Trie
void insert(const char* key) {
TrieNode* node = root;
for (int i = 0; key[i] != '\0'; i++) {
int index = key[i] - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->is_end_of_word = true; // Mark the end of the word
}
// Search for a word in the Trie
bool search(const char* key) {
TrieNode* node = root;
for (int i = 0; key[i] != '\0'; i++) {
int index = key[i] - 'a';
if (!node->children[index]) return false;
node = node->children[index];
}
return node != nullptr && node->is_end_of_word;
}
// Delete a word from the Trie
void deleteKey(const char* key) {
deleteHelper(root, key, 0, strlen(key));
}
};
int main() {
Trie trie;
trie.insert("hello");
trie.insert("world");
cout << "Search 'hello': " << (trie.search("hello") ? "Found" : "Not Found") << endl;
cout << "Search 'world': " << (trie.search("world") ? "Found" : "Not Found") << endl;
trie.deleteKey("hello");
cout << "Search 'hello' after deletion: " << (trie.search("hello") ? "Found" : "Not Found") << endl;
return 0;
}
Output:
2. Prefix Search in a List of Words
This program implements a trie structure for prefix and word search. A trie_node stores child pointers and a flag indicating the end of a word. The Trie class provides methods to insert words, check if a prefix exists, and verify if a word exists. Words are inserted by creating nodes for each character if they don't already exist. Prefix search traverses the trie to verify the existence of a given prefix. Word search checks if a word exists and ends at a marked node.
Code:
#include <iostream>
#include <cstring>
using namespace std;
// Trie Node structure
struct trie_node {
trie_node* children[26];
bool is_end_of_word;
trie_node() {
is_end_of_word = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
trie_node* root;
// Helper function to check if a node has any children
bool is_empty(trie_node* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) return false;
}
return true;
}
public:
Trie() {
root = new trie_node();
}
// Function to insert a word into the trie
void insert(const char* word) {
trie_node* current = root;
for (int i = 0; word[i] != '\0'; i++) {
int index = word[i] - 'a';
if (!current->children[index]) {
current->children[index] = new trie_node();
}
current = current->children[index];
}
current->is_end_of_word = true;
}
// Function to search for a prefix in the trie
bool search_prefix(const char* prefix) {
trie_node* current = root;
for (int i = 0; prefix[i] != '\0'; i++) {
int index = prefix[i] - 'a';
if (!current->children[index]) {
return false;
}
current = current->children[index];
}
return true;
}
// Function to check if a word exists in the trie
bool search_word(const char* word) {
trie_node* current = root;
for (int i = 0; word[i] != '\0'; i++) {
int index = word[i] - 'a';
if (!current->children[index]) {
return false;
}
current = current->children[index];
}
return current && current->is_end_of_word;
}
};
int main() {
Trie trie;
trie.insert("apple");
trie.insert("app");
trie.insert("bat");
cout << "Search prefix 'ap': " << (trie.search_prefix("ap") ? "Found" : "Not Found") << endl;
cout << "Search word 'apple': " << (trie.search_word("apple") ? "Found" : "Not Found") << endl;
cout << "Search prefix 'bat': " << (trie.search_prefix("bat") ? "Found" : "Not Found") << endl;
cout << "Search word 'cat': " << (trie.search_word("cat") ? "Found" : "Not Found") << endl;
return 0;
}
Output:
3. Longest Word in a Dictionary
This program implements a Trie data structure to solve the "longest word in a dictionary" problem. Words are inserted into the Trie, and the structure is used to find the longest valid word by recursively traversing the Trie. At each node, the function checks if it marks the end of a word and updates the result if the current word is longer or lexicographically smaller. The program outputs the longest valid word that can be built one character at a time using the dictionary.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 26
class Trie_Node {
public:
Trie_Node* children[MAX];
bool is_end_of_word;
Trie_Node() {
is_end_of_word = false;
for (int i = 0; i < MAX; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
Trie_Node* root;
public:
Trie() {
root = new Trie_Node();
}
// Insert a word into the Trie
void insert(const char* word) {
Trie_Node* current = root;
for (int i = 0; word[i] != '\0'; i++) {
int index = word[i] - 'a';
if (!current->children[index]) {
current->children[index] = new Trie_Node();
}
current = current->children[index];
}
current->is_end_of_word = true;
}
// Helper function to find the longest word in the Trie
void find_longest_word(Trie_Node* node, string current_word, string& longest_word) {
if (!node) return;
if (node->is_end_of_word) {
if (current_word.length() > longest_word.length() || (current_word.length() == longest_word.length() && current_word < longest_word)) {
longest_word = current_word;
}
}
for (int i = 0; i < MAX; i++) {
if (node->children[i]) {
find_longest_word(node->children[i], current_word + char('a' + i), longest_word);
}
}
}
// Start the process to find the longest word
string get_longest_word() {
string longest_word = "";
find_longest_word(root, "", longest_word);
return longest_word;
}
};
int main() {
Trie trie;
char words[][MAX] = {"w", "wo", "wor", "worl", "world"};
int word_count = 5;
for (int i = 0; i < word_count; i++) {
trie.insert(words[i]);
}
cout << "Longest Word: " << trie.get_longest_word();
return 0;
}
Output:
4. Replace Words in a Sentence
This program uses a trie to replace words in a sentence with their shortest prefixes from a given dictionary. The Trie class provides methods to insert dictionary words and find the shortest prefix for a given word. During processing, each word in the sentence is replaced by its shortest prefix using the trie. The result is the modified sentence with words replaced.
Code:
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
#define ALPHABET_SIZE 26
// Trie Node structure
class TrieNode {
public:
TrieNode* children[ALPHABET_SIZE];
bool is_end_of_word;
TrieNode() {
is_end_of_word = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
children[i] = nullptr;
}
}
};
// Trie class for managing the prefix dictionary
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
// Function to insert a word into the trie
void insert_word(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->is_end_of_word = true;
}
// Function to search for the shortest prefix in the trie
string get_shortest_prefix(const string& word) {
TrieNode* node = root;
string prefix = "";
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) break;
prefix += c;
node = node->children[index];
if (node->is_end_of_word) return prefix;
}
return word; // Return the original word if no prefix is found
}
};
// Function to replace words in a sentence using the trie
string replace_words(Trie& trie, const string& sentence) {
string result = "", word = "";
for (char c : sentence) {
if (c == ' ') {
result += trie.get_shortest_prefix(word) + " ";
word = "";
} else {
word += c;
}
}
result += trie.get_shortest_prefix(word); // Process the last word
return result;
}
int main() {
Trie trie;
int dictionary_size;
cout << "Enter the number of dictionary words: ";
cin >> dictionary_size;
cout << "Enter the dictionary words:" << endl;
for (int i = 0; i < dictionary_size; i++) {
string word;
cin >> word;
trie.insert_word(word);
}
cin.ignore(); // Clear input buffer
string sentence;
cout << "Enter the sentence: ";
getline(cin, sentence);
cout << "Modified Sentence: " << replace_words(trie, sentence) << endl;
return 0;
}
Output:
5. Implement Autocomplete System
This program implements an autocomplete system using a trie data structure. The insert method adds words to the trie, character by character, creating nodes as necessary. The autocomplete method traverses the trie based on the input prefix, and if the prefix exists, it calls the find_suggestions helper function to recursively collect all words starting with the prefix. Each complete word is printed as a suggestion.
Code:
#include <iostream>
#include <string>
using namespace std;
#define ALPHABET_SIZE 26
struct TrieNode {
TrieNode* children[ALPHABET_SIZE];
bool is_end_of_word;
TrieNode() {
is_end_of_word = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode* root;
// Helper function to recursively find suggestions
void find_suggestions(TrieNode* node, string prefix) {
if (node->is_end_of_word) {
cout << prefix << endl;
}
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (node->children[i]) {
find_suggestions(node->children[i], prefix + char(i + 'a'));
}
}
}
public:
Trie() {
root = new TrieNode();
}
// Insert a word into the trie
void insert(string word) {
TrieNode* current = root;
for (char c : word) {
int index = c - 'a';
if (!current->children[index]) {
current->children[index] = new TrieNode();
}
current = current->children[index];
}
current->is_end_of_word = true;
}
// Search for a word in the trie
bool search(string word) {
TrieNode* current = root;
for (char c : word) {
int index = c - 'a';
if (!current->children[index]) {
return false;
}
current = current->children[index];
}
return current->is_end_of_word;
}
// Display autocomplete suggestions for a given prefix
void autocomplete(string prefix) {
TrieNode* current = root;
for (char c : prefix) {
int index = c - 'a';
if (!current->children[index]) {
cout << "No suggestions found." << endl;
return;
}
current = current->children[index];
}
find_suggestions(current, prefix);
}
};
int main() {
Trie trie;
trie.insert("cat");
trie.insert("cap");
trie.insert("car");
trie.insert("dog");
trie.insert("bat");
string prefix;
cout << "Enter a prefix to autocomplete: ";
cin >> prefix;
cout << "Autocomplete suggestions: " << endl;
trie.autocomplete(prefix);
return 0;
}
Output:
Day 29 showcased the efficiency and utility of Tries in solving string manipulation problems and optimizing prefix-based searches. From implementing basic operations to building an autocomplete system, these challenges underscored the power of Tries in handling real-world applications involving structured text data. 🚀