Skip to content

Instantly share code, notes, and snippets.

@behitek
Forked from indrasaputra/trie.cpp
Created November 17, 2018 02:12
Show Gist options
  • Save behitek/acea6f2e99046dc32bfa25101e34433d to your computer and use it in GitHub Desktop.
Save behitek/acea6f2e99046dc32bfa25101e34433d to your computer and use it in GitHub Desktop.
Trie
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <utility>
#include <cctype>
#define MAX_SIZE 26
using namespace std;
struct Node
{
struct Node* children[MAX_SIZE];
bool isLeaf;
};
Node* createNewNode()
{
Node* newNode = new Node;
for(int i=0; i<MAX_SIZE; i++)
{
newNode->children[i] = NULL;
}
newNode->isLeaf = false;
return newNode;
}
void insertData(Node* root, string str)
{
int length = str.length();
for(int i=0; i<length; i++)
{
int character = str[i]-'a';
if(root->children[character] == NULL)
{
root->children[character] = createNewNode();
}
root = root->children[character];
}
root->isLeaf = true;
}
bool searchData(Node* root, string str)
{
int length = str.length();
for(int i=0; i<length; i++)
{
int character = str[i]-'a';
if(root->children[character] == NULL)
{
return false;
}
root = root->children[character];
}
return root->isLeaf;
}
int main()
{
Node* root = createNewNode();
insertData(root, "just");
insertData(root, "some");
insertData(root, "random");
insertData(root, "generated");
insertData(root, "strings");
printf("%s\n", searchData(root, "some") ? "Found" : "No");
printf("%s\n", searchData(root, "tests") ? "Found" : "No");
printf("%s\n", searchData(root, "for") ? "Found" : "No");
printf("%s\n", searchData(root, "the") ? "Found" : "No");
printf("%s\n", searchData(root, "strings") ? "Found" : "No");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment