This approach involves creating a basic Trie data structure using a tree of nodes. Each node represents a character in a word. Starting from a root node, each character of the word is inserted sequentially, with branches representing the progression to subsequent characters. This forms a chain of nodes (linked in a tree-like manner) from the root to the nodes representing complete words. For searching, we traverse these nodes based on the characters of the input word or prefix to check for existence.
Time Complexity: Insert, search, and startsWith operations are O(m), where m is the length of the word/prefix.
Space Complexity: O(26 * n * m) in the worst case, where n is the number of inserted words and m is the average length of the words. Each insertion can potentially add m nodes with 26 possible children each.
1typedef struct TrieNode {
2 struct TrieNode *children[26];
3 bool isEndOfWord;
4} TrieNode;
5
6TrieNode* createNode() {
7 TrieNode *node = (TrieNode *)malloc(sizeof(TrieNode));
8 node->isEndOfWord = false;
9 for(int i = 0; i < 26; i++)
10 node->children[i] = NULL;
11 return node;
12}
13
14typedef struct {
15 TrieNode *root;
16} Trie;
17
18Trie* trieCreate() {
19 Trie *trie = (Trie *)malloc(sizeof(Trie));
20 trie->root = createNode();
21 return trie;
22}
23
24void trieInsert(Trie* obj, char * word) {
25 TrieNode *node = obj->root;
26 while (*word) {
27 int index = *word - 'a';
28 if (!node->children[index])
29 node->children[index] = createNode();
30 node = node->children[index];
31 word++;
32 }
33 node->isEndOfWord = true;
34}
35
36bool trieSearch(Trie* obj, char * word) {
37 TrieNode *node = obj->root;
38 while (*word) {
39 int index = *word - 'a';
40 if (!node->children[index])
41 return false;
42 node = node->children[index];
43 word++;
44 }
45 return node->isEndOfWord;
46}
47
48bool trieStartsWith(Trie* obj, char * prefix) {
49 TrieNode *node = obj->root;
50 while (*prefix) {
51 int index = *prefix - 'a';
52 if (!node->children[index])
53 return false;
54 node = node->children[index];
55 prefix++;
56 }
57 return true;
58}
59
60void trieFree(Trie* obj) {
61 // A function to recursively free nodes would be here if needed.
62 free(obj);
63}We first define a TrieNode structure with a children array to hold 26 letters and a boolean isEndOfWord to check if a node marks the end of a word. The createNode function initializes each node. TrieCreate initializes the trie by setting the root node.
The methods work by converting each character of the word or prefix into an index (0-25 for 'a'-'z'), navigating the children array of nodes for insertion or search operations. The insert function loops through each character, generating nodes along the path if needed, setting the isEndOfWord flag at the end. The search verifies both existence and termination of the string in the Trie, while startsWith logic only requires the prefix traversal.
This approach relies on maps (or hashmaps) for storing children nodes dynamically. The advantage of using maps over arrays in this context arises from reduced space consumption when handling sparse trees since only existing characters are stored. Nodes manage their children using hash references, leading to more flexible branching.
Time Complexity: O(m) per operation where m is the word/prefix length.
Space Complexity: O(n * m), where n estimates the word count and m accounts for varying lengths since nodes only maintain necessary mappings.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
5
6class Trie:
7 def __init__(self):
8 self.root = TrieNode()
9
10 def insert(self, word: str) -> None:
11 node = self.root
12 for char in word:
13 node = node.children.setdefault(char, TrieNode())
14 node.is_end_of_word = True
15
16 def search(self, word: str) -> bool:
17 node = self.root
18 for char in word:
19 if char not in node.children:
20 return False
21 node = node.children[char]
22 return node.is_end_of_word
23
24 def startsWith(self, prefix: str) -> bool:
25 node = self.root
26 for char in prefix:
27 if char not in node.children:
28 return False
29 node = node.children[char]
30 return TrueIn this Python solution, each TrieNode contains a dictionary (children) providing direct access to only required child characters. This approach optimizes storage, especially reducing overhead when branching is sparse. The root provides the base node in the Trie. The insert method applies setdefault for dictionary operation - simplifying conditional insertion logic. Both search and startsWith check the presence of each character in sequence traversing the root to target node, utilizing dictionary fast access and probing methods.