判断前缀

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

Trie 存在的全部意义，就是快速回答前缀查询。startsWith 会检查是否有任意已存储的单词以给定前缀开头，它不关心这个前缀本身是否是一个完整插入的单词。

遍历过程与 search 几乎相同：从根节点开始，每次沿着一个字符对应的子节点前进。如果途中缺少某个字符，就没有已存储的单词以该前缀开头，因此返回 false。如果你遍历完所有字符而没有停下，答案就是 true，该节点下方的子树中至少包含一个已存储的单词。

与 search 唯一的区别是：最后不需要检查 isEndOfWord。遍历到前缀末尾就足够了。

挑战

简单

为 Trie 类添加一个 startsWith 方法。

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

如果某个已插入的单词以 prefix 开头，则返回 true（前缀可以匹配完整单词，也可以是较长单词的开头部分）。
否则返回 false。

亲手试试

#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"); }
        if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
    }
    return 0;
}

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

1简介

简介什么是 Trie？

2Trie 项目

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

3挑战练习

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

自己练习： C 在线编译器