1. Introduction
In today’s lecture, we will take an in-depth look at the Trie data structure using the C++ programming language,
and solve algorithm problems utilizing this structure. A Trie is an optimized data structure for storing and
searching strings, useful for solving various problems such as dictionary lookups, auto-completion, and prefix searches.
2. Introduction to Trie Data Structure
A Trie stores characters of strings at each node, and the paths between nodes represent the prefixes of specific strings.
This data structure allows for efficient string searching, with a basic time complexity of O(m),
where m is the length of the string to be searched.
2.1 Components of a Trie
The basic components of a Trie are as follows:
- Node: Each node contains a character and child nodes.
- Insert: Adds a new string to the Trie.
- Search: Searches for a specific string in the Trie.
- Delete: Deletes a specific string from the Trie.
2.2 Advantages and Disadvantages of a Trie
The advantage of a Trie is that it makes prefix searches easy. However, a disadvantage is that it can use a lot
of memory and can be complex to implement.
3. Problem Definition
The following is an algorithm problem.
Please write a program that outputs all words with a specific prefix from the given list of strings.
Problem Description
Input:
– Word list words: [“apple”, “app”, “application”, “bat”, “ban”, “band”]
– Specific prefix prefix: “ap”
Output:
– Strings with the prefix “ap”: [“apple”, “app”, “application”]
4. Problem Solving Process
4.1 Defining the Trie Class
First, we need to define a Trie node and implement the Trie class. Below is a basic implementation in C++.
#include
#include
#include
#include
using namespace std;
class TrieNode {
public:
unordered_map children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c]) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEndOfWord = true;
}
void searchByPrefix(const string& prefix, vector& result, string current, TrieNode* node) {
if (node->isEndOfWord) {
result.push_back(current);
}
for (const auto& pair : node->children) {
searchByPrefix(prefix, result, current + pair.first, pair.second);
}
}
vector getWordsWithPrefix(const string& prefix) {
TrieNode* node = root;
vector result;
for (char c : prefix) {
if (!node->children[c]) {
return result; // No words with the given prefix
}
node = node->children[c];
}
searchByPrefix(prefix, result, prefix, node);
return result;
}
};
4.2 Implementing the Main Function
Now, let’s implement the main function to insert words into the Trie and search for words with the prefix.
int main() {
Trie trie;
vector words = {"apple", "app", "application", "bat", "ban", "band"};
// Insert words into the trie
for (const string& word : words) {
trie.insert(word);
}
// Prefix to search
string prefix = "ap";
vector result = trie.getWordsWithPrefix(prefix);
// Print the result
cout << "Words with prefix '" << prefix << "': ";
for (const string& word : result) {
cout << word << " ";
}
cout << endl;
return 0;
}
5. Code Execution Results
When the above code is executed, the following results will be printed.
All words corresponding to the given prefix “ap” will be output as a list.
Words with prefix 'ap': apple app application
6. Conclusion
In this lecture, we implemented the Trie data structure using C++ and solved the problem of searching for
words with a specific prefix. Tries are very useful data structures for solving string-related algorithm problems,
and can be used in various application areas. In future lectures,
I hope to learn about various data structures and techniques that can serve as references for solving various
algorithm problems. Thank you.