Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
Sample Output
2
3
1
0
Map水过~
大家可以看看字典树~
字典树 又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = ""; Map<String, Integer> map = new HashMap<String, Integer>(); while (true) { str = sc.nextLine(); if (str.equals("")) { break; } String s = ""; for (int i = 0; i < str.length(); i++) { s = s + str.charAt(i); if (map.get(s) == null) { map.put(s, 1); } else { map.put(s, map.get(s) + 1); } } } while (sc.hasNext()) { str =sc.next(); if(map.get(str)==null){ System.out.println(0); }else{ System.out.println(map.get(str)); } } } }
