首页 > 试题广场 >

字典树的实现

[编程题]字典树的实现

热度指数：5726 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，可重复添加；void delete(String word)：删除word，如果word添加过多次，仅删除一次；boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。

输入描述:

输入包含多行，第一行一个整数m，代表操作次数。接下来m行，每行包含一个整数op，和一个字符串word。

输出描述:

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

示例1

输入

7
1 qwer
1 qwe
3 qwer
4 q
2 qwer
3 qwer
4 q

输出

YES
2
NO
1

备注:

要求时空复杂度均为

算法知识视频讲解

牛客883901697号

发表于 2024-06-18 14:38:36

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWr 展开全文

TonyBryant

发表于 2024-04-04 18:22:01

#include<bits/stdc++.h> using namespace std; const int N = 1e6+10; // 结点总出现数 int cnt; // 当前结点(第几个结点) int Tree[N][26]; // 结点路径记录表 int pass[N]; 展开全文

吴清忠201808271120204

发表于 2024-04-13 11:26:12

#include <array> #include <iostream> using namespace std; // 根据左神静态数组的思路写的, 不需要动态内存管理了 // https://www.bilibili.com/video/BV1Yu4y1Q7vR/?sp 展开全文

用心的ssr在摸鱼

发表于 2025-03-16 14:27:25

import sys class TrieNode: def __init__(self): self.nexts = {} self.e = 0 # 记录以该节点结尾的单词个数 self.p = 0 # 记录经过该节点的单词总数展开全文

牛客579577851号

发表于 2025-07-14 09:57:01

import java.io.*; /** * @author cat * @description https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b * @create 2025/7/14 09:02 * 展开全文