题目描述

维护一个字符串集合，支持两种操作：

“I x”向集合中插入一个字符串x；
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式
第一行包含整数N，表示操作数。

接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。

输出格式
对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。

每个结果占一行。

数据范围
1≤N≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1

算法1

什么是“Trie 树”？

Trie 树也叫“字典树”，这是一个树形结构。它是专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题,即匹配字符串
Trie 树主要有两个操作:
一个是将字符串集合构成Trie 树。这个过程分解开来的话，就是一个字符串插入到Trie 树的过程。
另一个是在Trie 树中查询一个字符串。

如何实现一棵Trie 树(建立一颗Trie 树)？

当我们在Trie 树中查找字符串的时候，我们就可以字符的ASCII码减去 “a” 的 ASCII码，迅速找到匹配的子节点的指针。比如， d 的ASCII码减去 a 的ASCII码就是 3，，那节点 d 的指针就存储在数组中下标为3的位置中。

如何存储一个Trie 树？

通过一个下标与字符一一映射的数组，来存储节点的指针。
假设我们的字符串只有从 a 到 z 这26个小写字母，我们在数组中下标为0的位置存储指向子节点 a 的指针，下标为1的位置存储指向子节点 b 的指针，以此类推，下标为25的位置，存储的是指向子节点 z 的指针。如果某个字符的子节点还在，我们就对应的下标的位置存储 null。

class TrieNode{
    char data;
    TridNode childNode[26];
}

在Trie树中，查找某个字符串的时间复杂度是多少？

如果要在一组字符串中，频繁地查询某些字符串，用Trie树是会非常高效。构建Trie树的过程，需要扫描所有的字符串，时间复杂度是O(n)（n表示所有字符串的长度和）。但是一旦构建成功之后，后续的查询操作会非常高效。

每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有身体倍棒关系。所以说，构建好Trie树后，在其中查找字符串的时间复杂度是O(k)，k 表示要查找的字符串的长度。

Trie树真的很耗内存吗？

Trie树是非常耗内存的，用的是一种空间换时间的思路.

Trie树在一组字符串中查找字符串的缺点

1.字符串中包含的字符集不能太大。如果字符集太大，那存储空间可能会浪费很多。即便可能优化，但也要付出牺牲查询、插入效率的代价。
2.要示字符串的前缀重合比较多，不然空间消耗会变大很多
3.如果要用Trie树解决问题，那我们就要自己从0开始实现一个Trie树。除非必须，一般不建议这样做。
4.通过指针串起来的数据是不连续的，而Trie树用到了指针，对缓存并不友好，性能上会打个折扣。

总结

实际上，Trie树只是不适全精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie树比较适合的是查找前缀匹配的字符串。

java 代码

import java.util.*;

public class Main {


    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        Trie trie = new Trie();
        int n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            String choice = sc.next();
            String key = sc.next();
            if("I".equals(choice)) {
                trie.insert(key);
            }else {
                System.out.println(trie.count(key));
            }
        }

    }

    private static class Trie {
        //基数，表示我这个字符串的字符种类数。这里假设是小写字母
        private int R = 26;
        private Node root;

        //trie的每个节点都要记录以此为终点的字符串的数量，以及跟它连接的下面的R个节点(当然正常情况下，大部分节点都是空的)
        private class Node {
            int val;
            //默认是指向R个空值
            Node[] next = new Node[R];
        }

        public Trie() {
            root = new Node();
        }

        //向trie中插入字符串
        public void insert(String key) {
            Node cur = root;
            for (int i = 0; i < key.length(); i++) {
                int nextIndex = key.charAt(i) - 'a';
                if(cur.next[nextIndex] == null) {
                    Node temp = new Node();
                    cur.next[nextIndex] = temp;
                }
                cur = cur.next[nextIndex];
            }
            cur.val++;
        }

        //统计key这个字符串出现的频次
        public int count(String key) {
            Node cur = root;
            for (int i = 0; i < key.length(); i++) {
                int nextIndex = key.charAt(i) - 'a';
                cur = cur.next[nextIndex];
                if(cur == null) {
                    return 0;
                }
            }
            return cur.val;
        }

        //查看key这个字符串是否存在
        public boolean search(String key) {
            return count(key) != 0;
        }

        //查看是否有字符串以prefix为前缀
        public boolean startsWith(String prefix) {
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                int nextIndex = prefix.charAt(i) - 'a';
                cur = cur.next[nextIndex];
                if(cur == null) {
                    return false;
                }
            }
            return true;
        }
    }

}