输入包含多行,第一行一个整数m,代表操作次数。接下来m行,每行包含一个整数op,和一个字符串word。
对于每次操作,如果op为3时,如果word在字典树中,请输出“YES”,否则输出“NO”;如果op为4时,请输出返回以word为前缀的单词数量,其它情况不输出。
7 1 qwer 1 qwe 3 qwer 4 q 2 qwer 3 qwer 4 q
YES 2 NO 1
要求时空复杂度均为
#include <stdlib.h> #include <stdbool.h> #include <string.h> #include <stdio.h> typedef struct tn { int pass; int end; struct tn **children; // 存放子节点的指针 } node; node *new_node() { node *new_node = malloc(sizeof(node)); new_node->pass = 0; new_node->end = 0; new_node->children = (node **) calloc(26, sizeof(node *)); return new_node; } void destroy_node(node *node) { free(node->children); free(node); } void destroy_whole_path(node *node) { for (int i = 0; i < 26; i++) { if (node->children[i] != NULL) { destroy_node(node->children[i]); } } destroy_node(node); } typedef node *trie; trie new_trie() { return new_node(); } void insert(trie trie, char *word) { if (word == NULL || strlen(word) == 0) { return; } int len = (int) strlen(word); node *cur = trie; cur->pass++; int path; for (int i = 0; i < len; i++) { path = word[i] - 'a'; if (cur->children[path] == NULL) { cur->children[path] = new_node(); } cur = cur->children[path]; cur->pass++; } cur->end++; } bool search(trie trie, char *word) { if (word == NULL || strlen(word) == 0) { return false; } node *cur = trie; int path; for (int i = 0; i < strlen(word); i++) { path = word[i] - 'a'; if (cur->children[path] == NULL) { return false; } cur = cur->children[path]; } return cur->end != 0; } void delete(trie trie, char *word) { if (!search(trie, word)) { return; } node *cur = trie, *next; cur->pass--; int path; for (int i = 0; i < strlen(word); i++) { path = word[i] - 'a'; if (--cur->children[path]->pass == 0) { next = cur->children[path]; cur->children[path] = NULL; destroy_whole_path(next); return; } cur = cur->children[path]; } cur->end--; } int prefixNumber(trie trie, char *word) { if (word == NULL || strlen(word) == 0) { return false; } node *cur = trie; int path; for (int i = 0; i < strlen(word); i++) { path = word[i] - 'a'; if (cur->children[path] == NULL) { return 0; } cur = cur->children[path]; } return cur->pass; } #define MAXLEN 21 int main(void) { trie trie = new_trie(); int n, op; char str[MAXLEN]; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%s", &op, str); if (op == 1) insert(trie, str); else if (op == 2) delete(trie, str); else if (op == 3) printf("%s\n", search(trie, str) ? "YES" : "NO"); else if (op == 4) printf("%d\n", prefixNumber(trie, str)); } destroy_node(trie); return 0; }