Search
Lesson 6 of 14 in Coddy's Tries - Data Structures Series #8 course.
Searching for a word is the natural opposite of insert: walk down from the root one character at a time, following the matching children. If at any point the current node has no child for the next character, the word is not in the trie and we can return false right away.
If we manage to walk through every character, we land on a node. The answer is whatever that node's isEndOfWord flag says. This is the critical distinction: after inserting "car", the path for "ca" exists in the trie, but search("ca") must still return false because no one marked that node as the end of a word.
Challenge
EasyAdd a method search to the Trie class.
It gets a string word and returns:
trueifwordwas inserted into the trie before.falseotherwise (including when only a prefix ofwordexists, or when only a longer word starting withwordis stored).
Try it yourself
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
}
return 0;
}