字典树的实现_

字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。

假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。

1. void insert(String word)：添加word，可重复添加；
2. void delete(String word)：删除word，如果word添加过多次，仅删除一次；
3. boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
4. int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。

现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。

对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。

数据范围：操作数满足 $0\le m \le 10^5$ ，字符串长度都满足 $0 \le n \le 20$

进阶：所有操作的时间复杂度都满足 $O(n)$

#include <errno.h> #include <stdbool.h> #include <unistd.h> #define OK 1 #define ERROR -1 #define MEMORY_OVERFLOW -2 typedef int Status; typedef struct TrieNode { int count; // 这个单词在字典(dictionary)中出现的次数 struct TrieNode* children[26]; } TrieNode, *PTrieNode; typedef struct { TrieNode* root; } Trie; Status InitTrie(Trie* trie) { if (!((*trie).root = (PTrieNode) calloc(1, sizeof(TrieNode)))) { fprintf(stderr, "InitTrie Memory Overflow: %s\n", strerror(errno)); exit(MEMORY_OVERFLOW); } return OK; } Status insert(Trie* trie, const char* const word) { PTrieNode p = (*trie).root; for (const char* c = word; *c; ++c) { if (!p->children[*c - 97]) p->children[*c - 97] = (PTrieNode) calloc(1, sizeof(TrieNode)); p = p->children[*c - 97]; } ++(*p).count; return OK; } bool search(Trie* trie, const char* const word) { PTrieNode p = (*trie).root; for (const char* c = word; *c; ++c) { if (!p->children[*c - 97]) return false; p = p->children[*c - 97]; } return (*p).count > 0; } int depth_first_search_algorithm(const PTrieNode root) { int i = 0, s = root->count; for (i = 0; i < 26; ++i) { if (!root->children[i]) continue; s += depth_first_search_algorithm(root->children[i]); } return s; } int prefixNumber(Trie* trie, const char* const prefix) { PTrieNode p = (*trie).root; for (const char* c = prefix; *c; ++c) { if (!p->children[*c - 97]) return 0; p = p->children[*c - 97]; } return depth_first_search_algorithm(p); } void rmWord(Trie* trie, const char* const word) { PTrieNode p = (*trie).root; for (const char* c = word; *c; ++c) { if (!p->children[*c - 97]) return; p = p->children[*c - 97]; } --(*p).count; } void destroy(TrieNode* root) { int i; for (i = 0; i < 26; ++i) { if (!root->children[i]) continue; destroy(root->children[i]); } free(root); } Status DestroyTrie(Trie* trie) { destroy(trie->root); return OK; } /** * * @param operators string字符串二维数组 the ops * @param operatorsRowLen int operators数组行数 * @param operatorsColLen int* operators数组列数 * @return string字符串一维数组 * @return int* returnSize 返回数组行数 */ char** trieU(char* ** operators, int operatorsRowLen, int* operatorsColLen, int* returnSize) { usleep(1000 * 1000 - 300000); Trie trie; InitTrie(&trie); char ** ans = (char**) calloc(1E5, sizeof(char*)); char tmp[5] = { 0 }; *returnSize = 0; int i, op, found, num; for (i = 0; i < operatorsRowLen; ++i) { op = atoi(**(operators + i)); switch (op) { case 1: insert(&trie, *(*(operators + i) + 1)); break; case 2: rmWord(&trie, *(*(operators + i) + 1)); break; case 3: found = search(&trie, *(*(operators + i) + 1)); *(ans + (*returnSize)) = (char*) calloc(10, sizeof(char)); strcpy(*(ans + (*returnSize)++), (found ? "YES" : "NO")); break; case 4: num = prefixNumber(&trie, *(*(operators + i) + 1)); sprintf(tmp, "%d", num); *(ans + (*returnSize)) = (char*) calloc(10, sizeof(char)); strcpy(*(ans + (*returnSize)++), tmp); break; default: fputs("illegal parameter!", stderr); break; } } return DestroyTrie(&trie), ans; }

字典树的实现

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题