# My solution in C, O(n)

• ``````struct TrieNode {
struct TrieNode * next[26]; // a - z
int nword;
int nstart;
};

/** Initialize your data structure here. */
struct TrieNode* trieCreate() {
struct TrieNode* ret = malloc(sizeof(struct TrieNode));
memset(ret->next, 0, sizeof(struct TrieNode*) * 26);
ret->nword = 0;
ret->nstart = 0;
return ret;
}

/** Inserts a word into the trie. */
void insert(struct TrieNode* root, char* word) {
if (root == NULL) return;
struct TrieNode* p = root;
for (int i = 0; i < strlen(word); ++i){
if (p->next[word[i] - 'a'] == NULL)
p->next[word[i] - 'a'] = trieCreate();
p = p->next[word[i] - 'a'];
(p->nstart)++;
}
(p->nword)++;
}

/** Returns if the word is in the trie. */
bool search(struct TrieNode* root, char* word) {
if (word == NULL) return true;
if (root == NULL) return false;
struct TrieNode* p = root;
for (int i = 0; i < strlen(word); ++i){
if (p->next[word[i] - 'a'] == NULL)
return false;
p = p->next[word[i] - 'a'];
}
return p->nword > 0;
}

/** Returns if there is any word in the trie
that starts with the given prefix. */
bool startsWith(struct TrieNode* root, char* prefix) {
if (prefix == NULL) return true;
if (root == NULL) return false;
struct TrieNode* p = root;
for (int i = 0; i < strlen(prefix); ++i){
if (p->next[prefix[i] - 'a'] == NULL)
return false;
p = p->next[prefix[i] - 'a'];
}
return p->nstart > 0;
}

/** Deallocates memory previously allocated for the TrieNode. */
void trieFree(struct TrieNode* root) {
if (root == NULL) return;
for (int i = 0; i < 26; ++i)
free(root->next[i]);
free(root);
}

// Your Trie object will be instantiated and called as such:
// struct TrieNode* node = trieCreate();
// insert(node, "somestring");
// search(node, "key");
// trieFree(node);``````

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