208. Implement Trie (Prefix Tree)

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
   

Example 1:

Input:
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
Output:
[null, null, true, false, true, null, true]
Explanation:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // return True
trie.search(“app”); // return False
trie.startsWith(“app”); // return True
trie.insert(“app”);
trie.search(“app”); // return True

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most $3\ast 10^4$ calls in total will be made to insert, search, and startsWith.

From: LeetCode
Link: 208. Implement Trie (Prefix Tree)

---

Solution:

Ideas：

1. TrieNode Structure:
Each node in the Trie is represented by a structure, TrieNode, which has the following components:

• An array of pointers, children, where each pointer corresponds to a letter in the English alphabet.
• A boolean flag, isEndOfWord, to signify whether a word ends at this node.

2. Trie Structure:
The Trie itself is represented by a structure, Trie, which holds a pointer to the root node of the Trie.

3. trieCreate:
This function initializes the Trie object and allocates memory for the root node of the Trie.

4. trieInsert:
This function inserts a word into the Trie. For each character in the word, it traverses down the Trie, creating new nodes if needed, until the end of the word is reached, at which point it sets the isEndOfWord flag to true.

5. trieSearch:
This function searches for a word in the Trie. It traverses down the Trie according to the characters in the word. If it reaches the end of the word and the isEndOfWord flag is true, the word exists in the Trie; otherwise, it doesn’t.

6. trieStartsWith:
This function checks whether there is any word in the Trie that starts with the given prefix. It traverses down the Trie according to the characters in the prefix. If it can traverse the entire prefix, then there exists a word in the Trie that starts with this prefix.

7. trieFree and freeNode:
These functions deallocate the memory used by the Trie and its nodes.

Code:

#define ALPHABET_SIZE 26typedef struct TrieNode {struct TrieNode *children[ALPHABET_SIZE];bool isEndOfWord;
} TrieNode;typedef struct {TrieNode *root;
} Trie;/** Initialize your data structure here. */
Trie* trieCreate() {Trie *trie = (Trie *)malloc(sizeof(Trie));trie->root = (TrieNode *)calloc(1, sizeof(TrieNode));return trie;
}/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char * word) {TrieNode *node = obj->root;for (int i = 0; word[i] != '\0'; i++) {int index = word[i] - 'a';if (!node->children[index])node->children[index] = (TrieNode *)calloc(1, sizeof(TrieNode));node = node->children[index];}node->isEndOfWord = true;
}/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char * word) {TrieNode *node = obj->root;for (int i = 0; word[i] != '\0'; i++) {int index = word[i] - 'a';if (!node->children[index])return false;node = node->children[index];}return node->isEndOfWord;
}/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char * prefix) {TrieNode *node = obj->root;for (int i = 0; prefix[i] != '\0'; i++) {int index = prefix[i] - 'a';if (!node->children[index])return false;node = node->children[index];}return true;
}void freeNode(TrieNode *node) {for(int i = 0; i < ALPHABET_SIZE; i++)if(node->children[i])freeNode(node->children[i]);free(node);
}/** Deallocates the memory allocated for the Trie object. */
void trieFree(Trie* obj) {if(!obj) return;freeNode(obj->root);free(obj);
}/*** Your Trie struct will be instantiated and called as such:* Trie* obj = trieCreate();* trieInsert(obj, word);* bool param_2 = trieSearch(obj, word);* bool param_3 = trieStartsWith(obj, prefix);* trieFree(obj);
*/