TRIES › INTRODUCTORY QUESTIONS
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →A word can be represented as a path from a root: the first character chooses the first edge, the second character chooses the next edge, and so on. Words with the same prefix share that part of the path. For example, apple and app use the same nodes for a, p, and p; apple only continues with l and e.
The path alone cannot distinguish a complete word from a prefix of a longer word. The node after the final p must therefore store a separate isEnd flag. Searching apple follows all five characters and checks that flag. Searching app follows only three characters and sees that the flag is false until app is inserted. startsWith is different only because reaching the final prefix node is enough; it does not require isEnd to be true.
| MEASURE | BOUND | WHY |
|---|---|---|
| Time | O(A) | Each operation examines each character in its argument once and performs constant-time array access. Summing those walks over the complete operation sequence counts each processed character once, so no character is charged twice. |
| Space | O(P), at most O(A) | The result strings are required output and are excluded from extra space. Each newly created node represents one previously missing prefix; shared prefixes reuse nodes, while the worst shape creates a new node for every inserted character, giving O(A) extra space. |
#include <string>
#include <vector>
using namespace std;
class TrieNode {
public:
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; ++i) {
children[i] = nullptr;
}
}
~TrieNode() {
for (int i = 0; i < 26; ++i) {
delete children[i];
}
}
};
class Trie {
public:
TrieNode* root;
Trie() : root(new TrieNode()) {}
~Trie() {
delete root;
}
void insert(const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEnd = true;
}
bool search(const string& word) const {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (node->children[index] == nullptr) {
return false;
}
node = node->children[index];
}
return node->isEnd;
}
bool startsWith(const string& prefix) const {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (node->children[index] == nullptr) {
return false;
}
node = node->children[index];
}
return true;
}
};
class Solution {
public:
vector<string> process(vector<string>& operations,
vector<vector<string>>& args) {
Trie* trie = nullptr;
vector<string> result;
for (int i = 0; i < static_cast<int>(operations.size()); ++i) {
const string& operation = operations[i];
if (operation == "Trie") {
delete trie;
trie = new Trie();
result.push_back("null");
} else if (operation == "insert") {
trie->insert(args[i][0]);
result.push_back("null");
} else if (operation == "search") {
result.push_back(trie->search(args[i][0]) ? "true" : "false");
} else if (operation == "startsWith") {
result.push_back(trie->startsWith(args[i][0]) ? "true" : "false");
}
}
delete trie;
return result;
}
};The insertion line that creates a child must appear before node moves forward. Once node points at the child, setting isEnd after the loop marks exactly the node for the complete word. The two query methods deliberately share the same traversal but end differently: search asks whether a word stops here, while startsWith asks only whether this path exists.
A fixed array is a natural choice for 26 lowercase letters because indexing is simple and predictable. A competent alternative stores only existing edges in an unordered_map. This can use less memory when most trie nodes have very few children, but each character now pays hashing and map-allocation overhead. It is a memory-oriented rearrangement, not an asymptotic improvement: traversal remains linear in the argument length.
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class SparseTrieNode {
public:
unordered_map<char, SparseTrieNode*> children;
bool isEnd = false;
~SparseTrieNode() {
for (auto& entry : children) {
delete entry.second;
}
}
};
class SparseTrie {
public:
SparseTrieNode* root = new SparseTrieNode();
~SparseTrie() {
delete root;
}
void insert(const string& word) {
SparseTrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new SparseTrieNode();
}
node = node->children[c];
}
node->isEnd = true;
}
bool search(const string& word) const {
const SparseTrieNode* node = root;
for (char c : word) {
auto it = node->children.find(c);
if (it == node->children.end()) {
return false;
}
node = it->second;
}
return node->isEnd;
}
bool startsWith(const string& prefix) const {
const SparseTrieNode* node = root;
for (char c : prefix) {
auto it = node->children.find(c);
if (it == node->children.end()) {
return false;
}
node = it->second;
}
return true;
}
};
class Solution {
public:
vector<string> process(vector<string>& operations,
vector<vector<string>>& args) {
SparseTrie* trie = nullptr;
vector<string> result;
for (int i = 0; i < static_cast<int>(operations.size()); ++i) {
const string& operation = operations[i];
if (operation == "Trie") {
delete trie;
trie = new SparseTrie();
result.push_back("null");
} else if (operation == "insert") {
trie->insert(args[i][0]);
result.push_back("null");
} else if (operation == "search") {
result.push_back(trie->search(args[i][0]) ? "true" : "false");
} else if (operation == "startsWith") {
result.push_back(trie->startsWith(args[i][0]) ? "true" : "false");
}
}
delete trie;
return result;
}
};