# A very concise solution accepted with 36ms in C, well-explained

• Trie is a very basic structure in accelerating the searching just like hash, check it in wiki and you will easily understand each move happening the the following.

• inserting a new node while there is no such;
• searching treating the character of the string as index of the child -> traversing the tree; when there is no such child just return false; when finished but the child is not labelled word (isWord==false) -> then just return false;

Both the space and time complexity is linear in searching while inserting will only take constant.

``````#define LEN 26
struct TrieNode
{
bool isWord;
struct TrieNode **children;
};

struct TrieNode* nodeMaker()
{
struct TrieNode *t = (struct TrieNode*)malloc(sizeof(struct TrieNode));
t->isWord = false;
int space = sizeof(struct TrieNode*)*LEN;
t->children = (struct TrieNode**)malloc(space);
memset(t->children, 0, space);
return t;
}
struct TrieNode* trieCreate()
{
return nodeMaker();
}

void insert(struct TrieNode *root, char *word)
{
for(int i = 0; word[i]; i++)
{
int index = word[i]-'a';
if(!(root->children[index])) //when there is no such child, create one;
root->children[index] = nodeMaker();
root = root->children[index];
}
root->isWord = true; //label this child as the leaf of the word;
}

struct TrieNode *findLeaf(struct TrieNode *root, char *word)
{
for(int i = 0; word[i]; i++) //following the word to traverse the tree;
{
root = root->children[word[i]-'a'];
if(!root) return false; //there is no corresponding child node;
}
return root; //at the end of the traversal, return the last node;
}

//AC - 36ms;
bool search(struct TrieNode *root, char *word)
{
root = findLeaf(root, word);
return root&&root->isWord; //check whether the node exists and it's the leaf of a word;
}

bool startsWith(struct TrieNode *root, char *prefix)
{
root = findLeaf(root, word);
return root; //check whether the node is valid;
}

void trieFree(struct TrieNode *root)
{
free(root->children);
free(root);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.