字典树 数组方式实现

作者:神秘网友 发布时间:2020-09-08 08:02:21

字典树 数组方式实现

字典树 数组方式实现

在词典中查找某个单词时,例如:boy,我们会先找到 ‘b’,然后找到 ‘o’,最后找到 ‘y’。这个过程的时间复杂度是 O(m),m 为单词的长度。
字典树是模拟这个过程的数据结构,十分高效。例如储存 do,dog,boy,bob,结构如下:

字典树 数组方式实现
可以看见,公共前缀仅储存了一遍 ,字典树在空间上的效率也很高。但若用本身的结构来存储仍然会占用大量空间,用数组来存储字典树可以以非常紧凑的方式节约大量空间。

代码

int pos = 1;
int trie[1000010][26];//存储下一个字符的位置
int num[1000010];//以此为前缀的单词的数量
//bool tail[1000010]; 标记某个字符是否为单词结尾

void insert(char str[]){
	int p = 0;
	for(int i = 0; str[i]; ++i){
		int n = str[i] - 'a';
		if(trie[p][n] == 0){
			trie[p][n] = pos++;
		}
		p = trie[p][n];
		num[p]++;
		//根据需要打上标记
		//if(str[i] && !str[i + 1]){
		//	tail[p] = true;
		//}
	}
}

int find(char str[]){//查找以某个字符串为前缀的单词数量
	int p = 0;
	for(int i = 0; str[i]; ++i){
		int n = str[i] - 'a';
		if(trie[p][n] == 0){
			return 0;
		}
		p = trie[p][n];		
	}
	return num[p];
}

字典树 数组方式实现相关教程

  1. C/C++基础题112.数组去重
  2. C/C++基础题111.数组翻转
  3. Python知识点5:元组、字典、集合
  4. 11 旋转数组的最小数字
  5. 面试小知识点
  6. 剑指offer-1 -- 二维数组中的查找 - C++
  7. Java通俗易懂30天 第6天:数组
  8. 稀疏数组转换