系列文章目录

---

---

前言

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。

---

描述
字典树又称为前缀树或者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为前缀的单词数量，其它情况不输出。

import java.util.*;public class Solution {/*** * @param operators string字符串二维数组 the ops* @return string字符串一维数组*/public String[] trieU (String[][] operators) {//计算结果集长度，并进行初始化int len=0;for(String[] opera:operators){if(opera[0].equals("3")||opera[0].equals("4")){len++;}}String[] res=new String[len];Trie trie=new Trie();int id=0;for(String[] opera:operators){if(opera[0].equals("1")){//添加单词trie.insert(opera[1]);}else if(opera[0].equals("2")){//删除单词trie.delete(opera[1]);}else if(opera[0].equals("3")){//查询单词是否存在res[id++]=trie.search(opera[1])?"YES":"NO";}else if(opera[0].equals("4")){//查找以word为前缀的单词数量String preNumber=String.valueOf(trie.prefixNumber(opera[1]));res[id++]=preNumber;}}return res;}class Trie{//构建字典树节点class TrieNode{//child数组记录所有子节点TrieNode[] child;//pre_number表示插入单词时，当前节点被访问次数int pre_number;//end表示当前节点是否是某个单词的末尾boolean end;TrieNode(){child=new TrieNode[26];pre_number=0;end=false;}}Trie(){}//初始化根节点TrieNode root=new TrieNode();//添加单词void insert(String word){TrieNode node=root;char[] arr=word.toCharArray();for(char c:arr){//如果子节点不存在，则新建if(node.child[c-'a']==null){node.child[c-'a']=new TrieNode();}//往子节点方向移动node=node.child[c-'a'];node.pre_number++;}node.end=true;}void delete(String word){TrieNode node=root;char[] arr=word.toCharArray();for(char c:arr){//往子节点方向移动，将访问次数减一node=node.child[c-'a'];node.pre_number--;}//如果访问次数为0，说明不存在该单词为前缀的单词，以及该单词if(node.pre_number==0){node.end=false;}}boolean search(String word){TrieNode node=root;char[] arr=word.toCharArray();for(char c:arr){//如果子节点不存在，说明不存在该单词if(node.child[c-'a']==null){return false;}node=node.child[c-'a'];}//如果前面的节点都存在，并且该节点末尾标识为true，则存在该单词return node.end;}int prefixNumber(String pre){TrieNode node=root;char[] arr=pre.toCharArray();for(char c:arr){//如果子节点不存在，说明不存在该前缀if(node.child[c-'a']==null){return 0;}node=node.child[c-'a'];}//返回以该单词为前缀的数量return node.pre_number;}}
}