描述
字典树又称为前缀树或者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）。
对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。
方法一
思路
哈希散列表；
使用map存储所给字符串，并统计字符串出现的次数；
插入操作：判断map中是否存在待插入字符串，存在则原数量加一，不存在，则加入map中，数量初始化为1；时间复杂度为
；
删除操作：判断map中是否存在待删除字符串，存在则原数量减一；时间复杂度为
查询字符串操作：查询map中是否存在待查询字符串，hash查找，时间复杂度为
查询前缀数操作：遍历map中所有的key，判断其是否以待查询前缀为前缀，是则记录；
由于JDK中的startWith()的时间复杂度为，L为前缀的长度，所有总的时间复杂度为
，n为map中的key数量。
空间复杂度：
,n为字符串数量。
代码如下：
import java.util.*; public class Solution { private static String YES = "YES"; private static String NO = "NO"; private Map<String,Integer> wordsMap = new HashMap<>(); // 添加word private void insert(String word){ if (word.length() == 0){ return; } // 添入map中 if (wordsMap.containsKey(word)){ wordsMap.put(word,wordsMap.get(word)+1); }else{ wordsMap.put(word,1); } } // 删除word,word在前缀树中是必然存在的 private void delete(String word){ if (wordsMap.containsKey(word)){ wordsMap.put(word,wordsMap.get(word)-1); } } // 查询word是否在字典树中出现过 private boolean search(String word){ if (wordsMap.containsKey(word)){ return wordsMap.get(word) != 0; } return false; } // 返回以字符串pre作为前缀的单词数量 private int prefixNumber(String pre){ int res = 0; for(String key : wordsMap.keySet()){ if (key.startsWith(pre)){ res = res + wordsMap.get(key); } } return res; } /** * * @param operators string字符串二维数组 the ops * @return string字符串一维数组 */ public String[] trieU (String[][] operators) { // write code here List<String> res = new ArrayList<>(); for(int i = 0;i < operators.length;++i){ switch(operators[i][0]){ // 插入 case "1": insert(operators[i][1]); break; // 删除 case "2": delete(operators[i][1]); break; // 查找单词 case "3": if (search(operators[i][1])){ res.add(YES); }else{ res.add(NO); } break; // 查找前缀 case "4": res.add(String.valueOf(prefixNumber(operators[i][1]))); break; } } String[] ans = new String[res.size()]; for (int i = 0;i < ans.length;++i){ ans[i] = res.get(i); } return ans; } }方法二
思路
前缀树；
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
叫前缀树应该更加直观吧，其具有以下三个基本性质：
1.根节点不包含字符，其余节点均只包含一个字符；
2.从根节点到指定节点的路径上的所有字符即为该节点对应的字符串；
3.每个节点的所有子节点包含的字符都不相同。前缀树包含以下四种方法：
1.插入函数，insert，时间复杂度为，l为插入字符串的长度；
2.删除函数：delete，时间复杂度为
3.查询字符串函数：search，时间复杂度为
4.查询字符串前缀函数：prefixNumber，时间复杂度为所以对与n个操作的总的时间复杂度为
,n为操作数，l为字符串平均长度。
空间复杂度：
,l为为字典树的深度；使用了长度为26的一维数组来存储每个节点的所有子节点。
具体实现：
1.所给字符串只有a~z这26个字符，所有对于一个字符节点其子节点只会在a~z中，即其最多有26个子节点，使用一维数组存储这26子节点；同时为了方便统计字符串的个数以及前缀被使用的个数，所以在节点类中使用记录以当前节点为结尾的字符串的个数count，以及以当前节点为结尾的前缀的个数prefix，类结构如下：// 前缀树的节点类 class TrieNode{ int count; int prefix; TrieNode[] nextNode = new TrieNode[CHARNUMBER]; public TrieNode(){ count = 0; prefix = 0; } }2.考虑前缀树的性质，对于插入操作，只需按照待插入字符串的字符顺序在前缀树中查找相应的前缀即可，若有对应的前缀字符，则更新prefix数，若没有对应的前缀则创建新的字符节点；同时在某位节点记录字符串数；参考下图示例：
3.删除函数，由于题目保证待删除字符串一定存在于字典树中，所以只需要找到对应的节点将其prefix数减一，同时将末尾节点的count数减一即可；
4.查询字符串，只需在字典树种依据字符串的字符顺序找到对应的前缀的末尾节点，看其count数是否为0，不为0则存在，反之不存在；若是不存在对应的前缀节点，则不存在该字符串；
5.查询前缀数，由于前缀在插入和删除时一直都有更新维护，所以在查找某一前缀数量时，只需找到前缀的末尾节点，其上的前缀数即为所查询的前缀数。代码如下：
import java.util.*; public class Solution { private static int CHARNUMBER = 26; private static String YES = "YES"; private static String NO = "NO"; // 前缀树的节点类 class TrieNode{ // 字符串数 int count; // 前缀树 int prefix; TrieNode[] nextNode = new TrieNode[CHARNUMBER]; public TrieNode(){ count = 0; prefix = 0; } } // 添加word private void insert(TrieNode root,String word){ if (root == null || word.length() == 0){ return; } // 转换成字符数组 char[] w = word.toCharArray(); for (Character c : w){ // 计算分支下标 int index = c - 'a'; // 如果分支不存在，创建一个新节点 if (root.nextNode[index] == null){ root.nextNode[index] = new TrieNode(); } root = root.nextNode[index]; // 以该节点之前的字符串为前缀的单词数量加一 // 根节点为空节点，所以需要在上述表达式之后加一 ++root.prefix; } // 以该节点结尾的单词数量加一 ++root.count; } // 删除word,word在前缀树中是必然存在的 private void delete(TrieNode root,String word){ char[] w = word.toCharArray(); for(Character c : w){ // 到末尾节点处 root = root.nextNode[c-'a']; --root.prefix; } // word的出现次数减一 --root.count; } // 查询word是否在字典树中出现过 private boolean search(TrieNode root,String word){ char[] w = word.toCharArray(); for(Character c : w){ // 到末尾节点处 int index = c - 'a'; if (root.nextNode[index] == null){ return false; } root = root.nextNode[index]; } // count = 0，表示没有该字符串，即不存在 return root.count != 0; } // 返回以字符串pre作为前缀的单词数量 private int prefixNumber(TrieNode root,String pre){ // 转换成字符数组 char[] w = pre.toCharArray(); for (Character c : w){ // 计算分支下标 int index = c - 'a'; // 如果分支不存在，创建一个新节点 if (root.nextNode[index] == null){ return 0; } root = root.nextNode[index]; } return root.prefix; } /** * * @param operators string字符串二维数组 the ops * @return string字符串一维数组 */ public String[] trieU (String[][] operators) { // write code here List<String> res = new ArrayList<>(); TrieNode root = new TrieNode(); for(int i = 0;i < operators.length;++i){ switch(operators[i][0]){ // 插入 case "1": insert(root,operators[i][1]); break; // 删除 case "2": delete(root,operators[i][1]); break; // 查找单词 case "3": if (search(root,operators[i][1])){ res.add(YES); }else{ res.add(NO); } break; // 查找前缀 case "4": res.add(String.valueOf(prefixNumber(root,operators[i][1]))); break; } } String[] ans = new String[res.size()]; for (int i = 0;i < ans.length;++i){ ans[i] = res.get(i); } return ans; } }
京公网安备 11010502036488号