AcWing 835. Trie字符串统计
原题链接
简单
个人理解
- Trie树又称为
字典树
,单词查找树
,是一种高效存储和查询字符串的数据结构。
- Trie树的题目中,构成字符串的单个字符一般都有范围限制,要么全是大写字母,要么全是小写字母
Trie树 数据结构的实现
- 我们先来看一下Trie树的实现方式,由一个
二维数组
,一个一维数组
,和一个下标
组成
int N = 1e5 + 10;
int[][] son = new int[N][26];
int[] cnt = new int[N];
int idx;
- 我们可以看到,Trie树的存储实际上是用一个二维数组son来模拟的,son数组的
第一维下标
表示当前结点的标识符,第二维下标
表示从当前结点可以到达的下一个字符集映射中的某一个字符
(将26个小写字母映射到整数0-25),而son[p][0]存储的值
则是从p结点可以到达的字符a的结点标识符。结点表示符由idx
来控制分配,由于idx
是递增的,所以分配不会重复。
而cnt用来存储以当前结点为结尾的单词在树中出现了多少次
。idx用来控制空间的分配,其中idx
的范围就是son数组第一维下标的范围。
下面看存储与插入代码的实现,结合上文进行理解
static void insert(String str) {
int p = 0; // 从0结点开始查找,0结点既是根结点,也是空结点
for (int i = 0; i < str.length(); i ++) {
int u = str.charAt(i) - 'a';
if (son[p][u] == 0) { // 值为0表示当前词链中不存在下一个字符
son[p][u] = ++idx;
}
p = son[p][u]; // 跳到下一个结点
}
cnt[p] ++;
}
static int query(String str) {
int p = 0;
for (int i = 0; i < str.length(); i ++) {
int u = str.charAt(i) - 'a';
if (son[p][u] == 0) {
return 0;
}
p = son[p][u];
}
return cnt[p];
}