搜索

Coddy 字典树：数据结构系列第 8 课课程的第 6 课，共 14 课。

查找单词是插入的自然反向操作：从根节点开始，每次沿着匹配的子节点向下走一个字符。如果当前节点没有下一个字符对应的子节点，那么这个单词不在字典树中，我们可以立即返回 false。

如果我们成功走完所有字符，就会到达一个节点。答案取决于该节点的 isEndOfWord 标记。这是关键区别：插入 "car" 后，字典树中存在 "ca" 的路径，但 search("ca") 仍必须返回 false，因为没有人将该节点标记为一个单词的结尾。

挑战

简单

为 Trie 类添加一个 search 方法。

它接收一个字符串 word，并返回：

如果之前已将 word 插入字典树，则返回 true。
否则返回 false（包括只存在 word 的前缀，或只存储了以 word 开头的更长单词的情况）。

亲手试试

#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;
}

字典树：数据结构系列第 8 课中的所有课

1简介

简介什么是 Trie？

2Trie 项目

TrieNode 类 Trie 类插入搜索判断前缀删除单词数量

3挑战练习

最长公共前缀统计前缀匹配的单词自动补全字典中的最长单词单词拆分

自己练习： C 在线编译器