[编程题]字典树的实现
- 热度指数：2017 时间限制：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
备注:
要求时空复杂度均为
纯coding的题目，只要理解Trie树的原理就很好实现
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class TrieNode {
public int pass;
public int end;
public TrieNode[] nexts;
public TrieNode() {
pass = 0;
end = 0;
nexts = new TrieNode[26];
}
}
class Trie {
public TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(char[] word) {
if(word == null) return;
TrieNode node = root;
node.pass ++;
int offset = 0;
for(int i = 0; i < word.length; i++){
offset = word[i] - 'a';
if(node.nexts[offset] == null) node.nexts[offset] = new TrieNode();
node = node.nexts[offset];
node.pass ++;
}
node.end ++;
}
public void delete(char[] word) {
if(search(word)){
// 加入过才删
TrieNode node = root;
int offset = 0;
for(int i = 0; i < word.length; i++){
offset = word[i] - 'a';
if(--node.nexts[offset].pass == 0){
// 当前字符直接没有了，后面的节点全部释放掉
node.nexts[offset] = null;
return;
}
node = node.nexts[offset];
}
node.end--;
}
}
public boolean search(char[] word) {
if(word == null) return false;
TrieNode node = root;
int offset = 0;
for(int i = 0; i < word.length; i++){
offset = word[i] - 'a';
if(node.nexts[offset] == null) return false;
node = node.nexts[offset];
}
return node.end > 0;
}
public int prefixNumber(char[] word) {
if(word == null) return 0;
TrieNode node = root;
int offset = 0;
for(int i = 0; i < word.length; i++){
offset = word[i] - 'a';
if(node.nexts[offset] == null) return 0;
node = node.nexts[offset];
}
return node.pass;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
Trie tree = new Trie();
for(int i = 0; i < n; i++){
String[] params = br.readLine().split(" ");
if(params[0].equals("1")){
tree.insert(params[1].toCharArray());
}else if(params[0].equals("2")){
tree.delete(params[1].toCharArray());
}else if(params[0].equals("3")){
System.out.println(tree.search(params[1].toCharArray())? "YES": "NO");
}else{
System.out.println(tree.prefixNumber(params[1].toCharArray()));
}
}
}
}
发表于 2021-11-13 23:26:25
回复(0)
#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;
}
发表于 2022-02-10 16:18:43
回复(0)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10; // 结点总出现数
int cnt; // 当前结点(第几个结点)
int Tree[N][26]; // 结点路径记录表
int pass[N]; // 该结点的通过数
int endd[N]; // 该结点作为末尾数
// 单词插入:
void word_insert(string word)
{
int tool=1; // 遍历工具 - 从第 1 个结点开始
int path=0; // 路径记录
pass[tool]++; // 第一个结点通过数++
// 遍历单词 从第二个结点开始记录
for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
{
path = c - 'a'; // 第 1 & 2 结点之间的路径
// 没有该结点:
if(Tree[tool][path]==0)
{
// 添加结点:
Tree[tool][path] = ++cnt;
// 遍历工具访问下一结点，结点通过数++
tool = Tree[tool][path];
pass[tool]++;
}
// 有对应结点:
else
{
// 遍历工具访问下一结点，结点通过数++
tool = Tree[tool][path];
pass[tool]++;
}
}
// 结点作为末尾数++
endd[tool]++;
return;
}
// 单词查重:
int word_duplicate(string word)
{
int tool=1; // 遍历工具 - 从第 1 个结点开始
int path=0; // 路径记录
// 遍历单词 从第二个结点开始记录
for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
{
path = c - 'a'; // 第 1 & 2 结点之间的路径
// 没有该结点:
if(Tree[tool][path]==0)
{
return 0;
}
// 有对应结点:
else
{
// 遍历工具访问下一结点，结点通过数++
tool = Tree[tool][path];
}
}
// 返回结点作为末尾数:
return endd[tool];
}
void word_delete(string word)
{
// 没有该单词
if(!word_duplicate(word))
{
return;
}
// 有该单词:
else
{
int tool=1; // 遍历工具 - 从第 1 个结点开始
int path=0; // 路径记录
pass[tool]--; // 第一个结点通过数++
// 遍历单词 从第二个结点开始记录
for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
{
path = c - 'a'; // 第 1 & 2 结点之间的路径
pass[Tree[tool][path]]--;
// 该路径没被复用过，仅仅记录一次:
if(pass[Tree[tool][path]]==0)
{
Tree[tool][path]=0;
return;
}
// 该路径被复用过:
else
{
tool = Tree[tool][path];
}
}
// 结点作为末尾数--
endd[tool]--;
return;
}
}
int word_pre(string word)
{
int tool=1; // 遍历工具 - 从第 1 个结点开始
int path=0; // 路径记录
// 遍历单词 从第二个结点开始记录
for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
{
path = c - 'a'; // 第 1 & 2 结点之间的路径
// 没有该结点:
if(Tree[tool][path]==0)
{
return 0;
}
// 有对应结点:
else
{
// 遍历工具访问下一结点
tool = Tree[tool][path];
}
}
// 返回结点通过数:
return pass[tool];
}
void clear()
{
memset(&Tree[0][0] , 0 , sizeof(int)*26*(cnt+1));
memset(&pass[0] , 0 , sizeof(int)*(cnt+1));
memset(&endd[0] , 0 , sizeof(int)*(cnt+1));
cnt=1;
}
int main()
{
cnt=1;
int n;
cin >> n;
while(n--)
{
int x;
string word;
cin >> x >> word;
if(x==1)
{
word_insert(word);
}
else if(x==2)
{
word_delete(word);
}
else if(x==3)
{
cout << (word_duplicate(word)>0 ? "YES" : "NO") << endl;
}
else
{
cout << word_pre(word) << endl;
}
}
clear();
return 0;
}
编辑于 2024-04-04 18:23:34
回复(0)
package class044;
// 用固定数组实现前缀树，空间使用是静态的。推荐！
// 测试链接 : https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
public class Code02_TrieTree {
// 如果将来增加了数据量，就改大这个值
public static int MAXN = 150001;
public static int[][] tree = new int[MAXN][26];
public static int[] end = new int[MAXN];
public static int[] pass = new int[MAXN];
public static int cnt;
public static void build() {
cnt = 1;
}
public static void insert(String word) {
int cur = 1;
pass[cur]++;
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
if (tree[cur][path] == 0) {
tree[cur][path] = ++cnt;
}
cur = tree[cur][path];
pass[cur]++;
}
end[cur]++;
}
public static int search(String word) {
int cur = 1;
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
if (tree[cur][path] == 0) {
return 0;
}
cur = tree[cur][path];
}
return end[cur];
}
public static int prefixNumber(String pre) {
int cur = 1;
for (int i = 0, path; i < pre.length(); i++) {
path = pre.charAt(i) - 'a';
if (tree[cur][path] == 0) {
return 0;
}
cur = tree[cur][path];
}
return pass[cur];
}
public static void delete(String word) {
if (search(word) > 0) {
int cur = 1;
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
if (--pass[tree[cur][path]] == 0) {
tree[cur][path] = 0;
return;
}
cur = tree[cur][path];
}
end[cur]--;
}
}
public static void clear() {
for (int i = 1; i <= cnt; i++) {
Arrays.fill(tree[i], 0);
end[i] = 0;
pass[i] = 0;
}
}
public static int m, op;
public static String[] splits;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String line = null;
while ((line = in.readLine()) != null) {
build();
m = Integer.valueOf(line);
for (int i = 1; i <= m; i++) {
splits = in.readLine().split(" ");
op = Integer.valueOf(splits[0]);
if (op == 1) {
insert(splits[1]);
} else if (op == 2) {
delete(splits[1]);
} else if (op == 3) {
out.println(search(splits[1]) > 0 ? "YES" : "NO");
} else if (op == 4) {
out.println(prefixNumber(splits[1]));
}
}
clear();
}
out.flush();
in.close();
out.close();
}
}
左程云的静态数组实现方式
关注左程云喵 关注左程云谢谢喵
发表于 2023-12-13 21:38:54
回复(0)
// 已经AC的代码
#include<iostream>
#include<string>
using namespace std;
void insert(string word);
void delete_(string word); // delete 是关键字，这里改为 delete_
bool search(string word);
int prefixNumber(string pre);
class TrieNode { // 在后续函数中全部改为指针形式
public:
int path = 0;
int end = 0;
TrieNode *map[26] = {NULL}; // 注意这里要加 * 号 ，注意一定要把指向对象的数组指向NULL
};
TrieNode *root = new TrieNode(); // 注意一定要写 new TrieNode()
void insert(string word) {
if (word.empty()) {
return;
}
TrieNode *node = root;
node->path++;
int index = 0;
for (int i = 0; i < word.size(); i++) {
index = word[i] - 'a';
if (node->map[index] == NULL) {
node->map[index] = new TrieNode();
}
node = node->map[index];
node->path++;
}
node->end++;
}
void delete_(string word) {
if (search(word)) {
TrieNode *node = root;
node->path++;
int index = 0;
for (int i = 0; i < word.size(); i++) {
index = word[i] - 'a';
if (node->map[index]->path-- == 1) {
node->map[index] = NULL;
return;
}
node = node->map[index];
}
node->end--;
}
}
bool search(string word) {
if (word.empty()) {
return false;
}
TrieNode *node = root;
int index = 0;
for (int i = 0; i < word.size(); i++) {
index = word[i] - 'a';
if (node->map[index] == NULL) {
return false;
}
node = node->map[index];
}
return node->end != 0;
}
int prefixNumber(string pre) {
if (pre.empty()) {
return 0;
}
TrieNode *node = root;
int index = 0;
for (int i = 0; i < pre.size(); i++) {
index = pre[i] - 'a';
if (node->map[index] == NULL) {
return 0;
}
node = node->map[index];
}
return node->path;
}
int main() {
int m;
cin >> m;
while (m--) {
int op;
cin >> op;
if (op == 1) {
string word;
cin >> word;
insert(word);
}
if (op == 2) {
string word;
cin >> word;
delete_(word);
}
if (op == 3) {
string word;
cin >> word;
bool res = search(word);
cout << (res ? "YES" : "NO") << endl;
}
if (op == 4) {
string word;
cin >> word;
int res = prefixNumber(word);
cout << res << endl;
}
}
return 0;
}
发表于 2020-09-07 14:02:15
回复(0)
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int N = 26;
class Node{
public:
Node();
~Node();
/*
void insert(string word);
void deleteStr(string word);
bool search(string word);
int prefixNumber(string pre);
*/
int pass;
int end;
Node *next[N];
};
Node::Node()
{
this->pass = 0;
this->end = 0;
memset(this->next,NULL,sizeof(next));
}
Node::~Node()
{
for(int i = 0; i < N; i++)
{
if(this->next[i] != NULL)
{
delete this->next[i];
this->next[i] = NULL;
}
}
}
bool search(Node * root ,string word);
//op = 1
void insert(Node * root , string word)
{
if(word.size() == 0)
return;
Node* node = root;
node->pass++;
int index = 0;
for(int i = 0; i < word.size() ; i++)
{
index = word[i] - 'a';
if(node->next[index] == NULL)
node->next[index] = new Node;
node = node->next[index];
node->pass++;
}
node->end++;
}
//op = 2
void deleteStr(Node *root ,string word)
{
if(!search(root,word))
return;
Node *node = root;
int index = 0;
node->pass--;
for(int i = 0; i < word.size(); i++)
{
index = word[i] - 'a';
node->next[index]->pass--;
if(node->next[index]->pass == 0)
{
delete node->next[index];
node->next[index] = NULL;
return;
}
node = node->next[index];
}
}
//op = 3
bool search(Node * root ,string word)
{
if(word.size() == 0)
return false;
Node *node = root;
int index = 0;
for(int i = 0 ; i < word.size() ; i++)
{
index = word[i] - 'a';
if(node->next[index] == NULL)
return false;
node = node->next[index];
}
return true;
}
//op = 4
int prefixNumber(Node * root ,string pre)
{
if(pre.size() == 0)
return root->pass;
Node *node = root;
int index = 0;
for(int i = 0; i < pre.size(); i++)
{
index = pre[i] - 'a';
node = node->next[index];
}
return node->pass;
}
int main(){
Node *root = new Node;
int m ;
cin >> m;
for(int i = 0; i < m; i++)
{
int op;
string str;
cin >> op;
cin >> str;
if(op == 1)
insert(root,str);
else if(op == 2)
deleteStr(root,str);
else if(op == 3)
cout << (search(root,str) ? "YES" : "NO") << endl;
else if(op == 4)
cout << prefixNumber(root,str) << endl;
}
delete root;
return 0;
}
有哪位大神能帮我看看，为什么我这个会发生段错误，谢谢
发表于 2020-02-09 23:59:09
回复(0)
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
// 根节点
private static TireNode root = new TireNode();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int opNum = in.nextInt();
while (opNum-- > 0) {
int op = in.nextInt();
String str = in.next();
switch (op) {
case 1:
addNode(str);
break;
case 2:
delNode(str);
break;
case 3:
System.out.println(ifExitNode(str) ? "YES" : "NO");
break;
case 4:
System.out.println(getSubNodeCnt(str));
}
}
}
private static int getSubNodeCnt(String prefix) {
TireNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.subNode.containsKey(c)) {
return 0;
}
node = node.subNode.get(c);
}
return node.cnt;
}
private static boolean ifExitNode(String str) {
TireNode node = root;
for (char c : str.toCharArray()) {
if (!node.subNode.containsKey(c)) {
return false;
}
node = node.subNode.get(c);
}
return node.end != 0;
}
// 删除node的时候 每次只能删一个 即使重复了好几个 每次也只能删一个
private static void delNode(String str) {
TireNode node = root;
for (char c : str.toCharArray()) {
node = node.subNode.get(c);
node.cnt--;
}
node.end--;
if (node.cnt == 0) {
node.subNode = new HashMap<>();
}
}
// 可以重复添加的node
private static void addNode(String str) {
TireNode node = root;
for (char c : str.toCharArray()) {
if (!node.subNode.containsKey(c)) {
node.subNode.put(c, new TireNode());
}
node = node.subNode.get(c);
node.cnt++;
}
node.end++;
}
static class TireNode {
// 其实可以换成数组
public Map<Character, TireNode> subNode = new HashMap<>();
// 多少个单词路过这个节点
public int cnt = 0;
// 这个节点是多少个单词的结尾
// 这点可以重复添加，这是最骚的
public int end = 0;
}
}
发表于 2019-08-19 22:17:17
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-20 14:55:10
-
2022-11-04 11:41:36
-
2022-09-05 22:59:51
-
2022-08-13 22:54:34 -
2022-08-10 09:47:56
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
