电子建设网站的目的,阿里巴巴网站是用什么技术做的,重庆网站推广软件,怎么通过ip查看自己做的网站数据结构、算法总述#xff1a;数据结构/基础算法 C/C_禊月初三的博客-CSDN博客 字典树#xff0c;英文名 trie。顾名思义#xff0c;就是一个像字典一样的树。 Trie 树是一种多叉树的结构#xff0c;它的特点是所有的字符都存储在树的分支上#xff0c;并且从根节点到某…数据结构、算法总述数据结构/基础算法 C/C_禊月初三的博客-CSDN博客 字典树英文名 trie。顾名思义就是一个像字典一样的树。 Trie 树是一种多叉树的结构它的特点是所有的字符都存储在树的分支上并且从根节点到某个叶节点的路径上的字符组成了一个字符串。 算法模板
int son[N][26], cnt[N], idx;
// 0号点既是根节点又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
void insert(string str)
{int p 0;for (int i 0; str[i]; i ){int u str[i] - a;if (!son[p][u]) son[p][u] idx;p son[p][u];}cnt[p] ;
}// 查询字符串出现的次数
int query(string str)
{int p 0;for (int i 0; str[i]; i ){int u str[i] - a;if (!son[p][u]) return 0;p son[p][u];}return cnt[p];
}
题目
1455. 检查单词是否为句中其他单词的前缀 - 力扣LeetCodehttps://leetcode.cn/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/description/
Trie树的主要优点是 搜索效率高搜索一个字符串的时间复杂度与字符串的长度成线性关系即O(L)其中L是字符串的长度。插入和删除效率高在Trie树中插入或删除一个字符串也具有O(L)的时间复杂度。节省空间Trie树不像数组那样需要为所有可能的字符串预留空间因此它可以更有效地利用内存。 Trie树的缺点是 空间复杂度较高由于每个字符都可能是一个节点的分支因此对于包含大量字符串的数据集Trie树可能会占用较多的内存。节点数量较多在Trie树中节点数量通常比字符串的数量多因为在树中每个字符串的每个字符都对应一个节点。
