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.
1class TrieNode {
2public:
3 TrieNode* children[26];
4 bool isEndOfWord;
5
6 TrieNode() {
7 isEndOfWord = false;
8 for (int i = 0; i < 26; ++i) {
9 children[i] = nullptr;
10 }
11 }
12};
13
14class Trie {
15public:
16 TrieNode* root;
17
18 Trie() {
19 root = new TrieNode();
20 }
21
22 void insert(string word) {
23 TrieNode* node = root;
24 for (char c : word) {
25 int index = c - 'a';
26 if (!node->children[index]) {
27 node->children[index] = new TrieNode();
28 }
29 node = node->children[index];
30 }
31 node->isEndOfWord = true;
32 }
33
34 bool search(string word) {
35 TrieNode* node = root;
36 for (char c : word) {
37 int index = c - 'a';
38 if (!node->children[index]) {
39 return false;
40 }
41 node = node->children[index];
42 }
43 return node->isEndOfWord;
44 }
45
46 bool startsWith(string prefix) {
47 TrieNode* node = root;
48 for (char c : prefix) {
49 int index = c - 'a';
50 if (!node->children[index]) {
51 return false;
52 }
53 node = node->children[index];
54 }
55 return true;
56 }
57};This C++ implementation uses a TrieNode class with a child array for connectivity and an isEndOfWord boolean. The Trie class maintains a root pointer. The insert function navigates through each character's node in string word, creating nodes as needed, and marks the node of the last character as an end of a word. The search function checks character by character and ensures the final node is marked as an end of a word. Similarly, startsWith checks for the path defined by prefix characters, confirming node existence up to the prefix's final node.
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.
1#include <unordered_map>
2using namespace std;
3
4class TrieNode {
5public:
6 unordered_map<char, TrieNode*> children;
7 bool isEndOfWord;
8
9 TrieNode() : isEndOfWord(false) {}
10};
11
12class Trie {
13public:
14 TrieNode* root;
15
16 Trie() {
17 root = new TrieNode();
18 }
19
20 void insert(string word) {
21 TrieNode* node = root;
22 for (char c : word) {
23 if (node->children.find(c) == node->children.end()) {
24 node->children[c] = new TrieNode();
25 }
26 node = node->children[c];
27 }
28 node->isEndOfWord = true;
29 }
30
31 bool search(string word) {
32 TrieNode* node = root;
33 for (char c : word) {
34 if (node->children.find(c) == node->children.end()) {
35 return false;
36 }
37 node = node->children[c];
38 }
39 return node->isEndOfWord;
40 }
41
42 bool startsWith(string prefix) {
43 TrieNode* node = root;
44 for (char c : prefix) {
45 if (node->children.find(c) == node->children.end()) {
46 return false;
47 }
48 node = node->children[c];
49 }
50 return true;
51 }
52};This C++ implementation employs unordered_map in place of fixed-arrays to maintain child nodes in a Trie. Each TrieNode can dynamically allocate space only for characters that appear, leading to memory efficiency especially when nodes have very few immediate child nodes compared to the alphabet size. Insert, search, and startsWith operate similarly as before, now using map functionalities (find) to identify existing children and allocate if necessary.