38 if (ch >=
'A' && ch <=
'Z') {
40 }
else if (ch >=
'a' && ch <=
'z') {
44 std::cerr <<
"Invalid character present. Exiting...";
45 std::exit(EXIT_FAILURE);
55 bool search(
const std::shared_ptr<trie>& root,
const std::string& str,
57 if (index == str.length()) {
58 if (!root->isEndofWord) {
67 return search(root->arr[j], str, index + 1);
76 void insert(
const std::string& str) {
77 std::shared_ptr<trie> root(
nullptr);
79 for (
const char& ch : str) {
85 std::shared_ptr<trie> temp(
new trie());
92 std::shared_ptr<trie> temp(
new trie());
97 root->isEndofWord =
true;
106 bool search(
const std::string& str,
int index) {
107 if (index == str.length()) {
134 if (index == str.length()) {
166 std::cout << __func__ <<
":" << __LINE__
167 <<
"Should not reach this line\n";
180 root.insert(
"World");
182 assert(!root.search(
"hello", 0));
183 std::cout <<
"hello - " << root.search(
"hello", 0) <<
"\n";
185 assert(root.search(
"Hello", 0));
186 std::cout <<
"Hello - " << root.search(
"Hello", 0) <<
"\n";
188 assert(!root.search(
"Word", 0));
189 std::cout <<
"Word - " << root.search(
"Word", 0) <<
"\n";
191 assert(root.search(
"World", 0));
192 std::cout <<
"World - " << root.search(
"World", 0) <<
"\n";
Trie implementation for small-case English alphabets a-z
void insert(const std::string &str)
std::array< std::shared_ptr< trie >, NUM_CHARS<< 1 > arr
Recursive tree nodes as an array of shared-pointers.
bool search(const std::string &str, int index)
static constexpr uint8_t NUM_CHARS
Number of alphabets.
bool isEndofWord
identifier if a node is terminal node
trie()=default
Class default constructor.
bool search(const std::shared_ptr< trie > &root, const std::string &str, int index)
uint8_t char_to_int(const char &ch) const
Convert a character to integer for indexing.
bool deleteString(const std::string &str, int index)
static void test()
Testing function.