Car Hidden Inside Cart
bool contains(Node* root, const string& w) {
Node* cur = root;
for (char c : w) {
int i = c - 'a';
if (!cur->next[i]) return false;
cur = cur->next[i];
}
return cur->childCount == 0; // "a leaf means a word ended here"
}
The trie is built by inserting "cart" and then "car", and insertion maintains childCount correctly but stores no end-of-word flag. What do contains(root, "car") and contains(root, "cart") return?
Sign in to answer questions and track your progress
Sign In