Introduction
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample
input
banana band bee absolute acm ba b band abc
output
2 3 1 0
Solution
package week3; import java.util.HashMap; import java.util.Scanner; /** * @author liangyuanshao * @date 2022/5/3 - 9:02 */ public class Main { public static class TrieTree{ public TrieTreeNode root=new TrieTreeNode(); class TrieTreeNode{ int path=0; int end=0; HashMap<Character,TrieTreeNode> nodeMap=new HashMap<>(); } public void insertString(String string){ if(string.equals("")||string==null)return; int len=string.length(); TrieTreeNode node=root; for(int i=0;i<len;i++){ char ch=string.charAt(i); HashMap<Character,TrieTreeNode> nodeMap=node.nodeMap; if(!nodeMap.containsKey(ch)){ TrieTreeNode newNode=new TrieTreeNode(); nodeMap.put(ch,newNode); } node.path++; node=nodeMap.get(ch); } node.path++; node.end++; } public int getPrefixNum(String string){ int len=string.length(); TrieTreeNode node=root; for(int i=0;i<len;i++){ char ch=string.charAt(i); TrieTreeNode newNode=node.nodeMap.get(ch); if(newNode==null){ return 0; } node=newNode; } return node.path; } } public static void main(String[] args) { Scanner s=new Scanner(System.in); TrieTree trieTree=new TrieTree(); while (true){ String string=s.nextLine(); if(string.equals("")){ break; } trieTree.insertString(string); } while (s.hasNext()){ String string=s.nextLine(); System.out.println(trieTree.getPrefixNum(string)); } } }
Experience
第一次使用字典树，所以开始搜了java如何构造字典树。
前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高
