首页 » 漏洞 » 字典树的应用

字典树的应用

 

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

##Sample Input banana band bee absolute acm  ba b band abc  ```  ##Sample Output

2

3

1

0

```

字典树的应用

这里用到前缀树。前缀树的特点是,根节点为空,为它添加子节点时,以字母为键,子节点可以指定出现次数。

//字典树(前缀 Trie)         var trie = {}           function add(trie, str) { //构建一个trie             for (var i = 0, n = str.length; i < n; i++) {                 var c = str[i]                 if (trie[c] == null) {                     trie[c] = {                         val: c,                         deep: i,                         appearCount: 1                     }                     trie = trie[c]                 } else {                     trie = trie[c]                     trie.appearCount++                 }             }          }          add(trie, "banana")         add(trie, "band")         add(trie, "bee")         add(trie, "absolute")         add(trie, "acm")          console.log(trie)          function has(trie, str) {             for (var i = 0, n = str.length; i < n; i++) {                 var c = str[i]                 if (c in trie) {                     trie = trie[c]                     if (i === n - 1) {                         console.log(trie.appearCount)                         return trie.appearCount                     }                 } else {                     console.log(0)                     return 0                 }             }             console.log(0) //0为找不到             return 0         }         console.log('answer:')         has(trie, 'ba')         has(trie, 'b')         has(trie, 'band')         has(trie, 'abc')

原文链接:字典树的应用,转载请注明来源!

0