首页 > 试题广场 >

字典树的实现

[编程题]字典树的实现

热度指数：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

备注:

要求时空复杂度均为

算法知识视频讲解

Java

想蹲进程

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)

Java

pein531

纯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)