Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Classes | |
struct | TrieNode |
Public Member Functions | |
Trie () | |
constructor to initialise the root of the trie. | |
void | insert (const std::string &word) |
bool | search (const std::string &word) |
void | removeWord (const std::string &word) |
Private Member Functions | |
std::shared_ptr< TrieNode > | removeWordHelper (const std::string &word, std::shared_ptr< TrieNode > curr, size_t index) |
Static Private Member Functions | |
static bool | hasChildren (std::shared_ptr< TrieNode > node) |
Private Attributes | |
std::shared_ptr< TrieNode > | m_root |
Static Private Attributes | |
static constexpr size_t | ALPHABETS = 26 |
A basic implementation of trie class to store only lower-case strings. You can extend the implementation to all the ASCII characters by changing the value of @ ALPHABETS to 128.
|
inline |
constructor to initialise the root of the trie.
|
inlinestaticprivate |
Function to check if a node has some children which can form words.
node | whose character array of pointers need to be checked for children. |
true
if a child is found false
if a child is not found
|
inline |
Insert a word into the trie.
word | which needs to be inserted into the string. |
|
inline |
|
inlineprivate |
A recursive helper function to remove a word from the trie. First, it recursively traverses to the location of last character of word in the trie. However, if the word is not found, the function returns a runtime error. Upon successfully reaching the last character of word in trie, if sets the isEndOfWord to false and deletes the node if and only if it has no children, else it returns the current node.
word | is the string which needs to be removed from trie. |
curr | is the current node we are at. |
index | is the index of the @word we are at. |
a | runtime error in case @ word is not found in the trie. |
|
inline |
Search if a word is present in trie or not.
word | which is needed to be searched in the trie. |