Leetcode-208. 实现Trie(前缀树)

ops/2024/12/23 18:42:09/

前缀树是一个由“路径”和“节点”组成多叉树结构。由根节点出发,按照存储字符串的每个字符,创建对应字符路径,以此实现快速查找单词或是否为前缀的功能。

此题要求简单,只需实现下面几种功能:

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。

因此有简单的实现方法。

package mainimport "fmt"type Trie struct {//结束标志isEnd    bool//子节点使用大小为26的数组存储children [26]*Trie
}func Constructor() Trie {return Trie{}
}//插入节点
func (this *Trie) Insert(word string) {node := this//遍历单词,确定依次向下的节点for _, ch := range word {//确定路径位置,即应该放到数组哪个位置path := ch - 'a'if node.children[path] == nil {//若不存在这个位置,则创建node.children[path] = &Trie{}}//向下移动node = node.children[path]}//结尾标志置位truenode.isEnd = true
}//搜索前缀
func (this *Trie) SearchPrefix(prefix string) *Trie {node := thisfor _, ch := range prefix {path := ch - 'a'if node.children[path] == nil {return nil}node = node.children[path]}return node
}//若能找到前缀并且isEnd为true,则找到这个单词
func (this *Trie) Search(word string) bool {node := this.SearchPrefix(word)return node != nil && node.isEnd
}func (this *Trie) StartsWith(prefix string) bool {return this.SearchPrefix(prefix) != nil
}func main() {T := Constructor()T.Insert("hello")T.Insert("how")T.Insert("heihei")if ok := T.Search("how"); ok {fmt.Println("成功找到")} else {fmt.Println("meiyou找到")}
}

通用实现:

type TrieNode struct {//经过节点的数量pass int//以当前节点为终点的单词数量end  intnext [26]*TrieNode
}type Trie struct {root *TrieNode
}// 初始化前缀树
func NewTrie() *Trie {return &Trie{root: &TrieNode{},}
}// 向前缀树中插入单词
func (t *Trie) Insert(word string) {if len(word) == 0 {return}node := t.rootnode.pass++for _, char := range word {index := char - 'a'if node.next[index] == nil {node.next[index] = &TrieNode{}}node = node.next[index]node.pass++}node.end++
}// 查找单词是否在前缀树中存在
func (t *Trie) Search(word string) bool {node := t.rootfor _, char := range word {index := char - 'a'if node.next[index] == nil {return false}node = node.next[index]}return node.end > 0
}// 检查是否有以给定前缀开头的单词存在于前缀树中
func (t *Trie) StartsWith(prefix string) bool {node := t.rootfor _, char := range prefix {index := char - 'a'if node.next[index] == nil {return false}node = node.next[index]}return node.pass > 0
}// 获取以某个前缀开头的单词数量
func (t *Trie) CountWordsWithPrefix(prefix string) int {node := t.rootfor _, char := range prefix {index := char - 'a'if node.next[index] == nil {return 0}node = node.next[index]}return node.pass
}// 获取某个单词出现的次数
func (t *Trie) CountWordOccurrences(word string) int {node := t.rootfor _, char := range word {index := char - 'a'if node.next[index] == nil {return 0}node = node.next[index]}return node.end
}// 删除单词
func (t *Trie) Delete(word string) {if!t.Search(word) {return}node := t.rootnode.pass--for _, char := range word {index := char - 'a'child := node.next[index]if child.pass == 1 {// 如果经过这个子节点的次数为1,说明只有当前要删除的单词经过它,直接删除该子节点node.next[index] = nilreturn}child.pass--if child.end > 0 && child.pass == 0 {// 如果当前子节点是某个单词结尾且经过次数变为0了,说明要删除的单词是最后经过它的单词,将其end置0child.end = 0return}node = child}node.end--
}

测试:

func main() {trie := NewTrie()trie.Insert("apple")trie.Insert("app")trie.Insert("banana")println(trie.Search("apple"))println(trie.Search("app"))println(trie.Search("banana"))trie.Delete("apple")println("After deleting 'apple':")println(trie.Search("apple"))println(trie.CountWordsWithPrefix("app"))println(trie.CountWordOccurrences("apple"))trie.Delete("app")println("After deleting 'app':")println(trie.Search("app"))println(trie.CountWordsWithPrefix("app"))println(trie.CountWordOccurrences("app"))
}


http://www.ppmy.cn/ops/144361.html

相关文章

AMS1117芯片驱动电路·降压芯片的驱动电路详解

目录 AMS1117常见封装 AMS1117不同系列 AMS1117驱动电路 参考数据手册 编写不易,仅供学习,请勿搬运,感谢理解 相同LDO芯片驱动专栏文章 LM7805系列降压芯片驱动电路降压芯片驱动电路详解-CSDN博客 ME6211C系列降压芯片驱动电路降压芯片…

浏览器引入elasticsearch-head插件

elasticsearch-head插件下载: 链接: https://pan.baidu.com/s/1Dz3aU42HZCNg45iJoDOsMg?pwduvhg 提取码: uvhg 1、打开浏览器设置 2、选择拓展程序 3、选择elasticsearch-head插件下载 4、打开es-head插件 5、修改ip 6、登录

Neo4j 图数据库安装与操作指南(以mac为例)

目录 一、安装前提条件 1.1 Java环境 1.2 Homebrew(可选) 二、下载并安装Neo4j 2.1 从官方网站下载 2.1.1 访问Neo4j的官方网站 2.1.2 使用Homebrew安装 三、配置Neo4j 3.1 设置环境变量(可选) 3.2 打开配置文件(bash_profile) 3.2.1 打开终端…

环境变革下 B2B 销售的转型与创新:开源 AI 智能名片与 S2B2C 商城小程序的助力

摘要:本文探讨了在信息科技与互联网迅猛发展所引发的环境改变背景下,B2B 销售工作面临的挑战与机遇。深入分析了传统销售模式的局限性以及新环境对销售人员素质和能力的要求,提出从提供“信息”向提供“业务价值”转变的必要性。同时&#xf…

前端海报生成的不同方案和优劣

加入我们一起学习,天天进步 一、背景 工作中做了很多生成海报的功能,不同需求,不同场景,使用了几种方案,各有优劣。一直想要整理一下,但这个过程中的思考和遇到的问题没有记录下来,比如图片的跨…

Ubuntu硬盘分区及挂载(命令行)

文章目录 一、简介二、硬盘分区三、格式化分区四、自动挂载分区五、调整分区大小小结 一、简介 创建磁盘分区首先需要找出Linux系统中的物理磁盘,在Linux中采用了一种标准格式来为硬盘分配设备名称。 SATA驱动器和SCSI驱动器:设备命名格式为/dev/sdx&a…

0.gitlab ubuntu20.04 部署问题解决

安装依赖: ① sudo apt-get update 出现: 解决方式: 去 /etc/apt/sources.list.d 这个目录删除或注释对应的list文件 第三方软件的源一般都以list文件的方式放在 /etc/apt/sources.list.d 这个目录 重新运行sudo apt-get update 安装…

sql-labs(21-25)

第21关 第一步 可以发现cookie是经过64位加密的 我们试试在这里注入 选择给他编码 发现可以成功注入 爆出表名 爆出字段 爆出数据 第22关 跟二十一关一模一样 闭合换成" 第 23 关 第二十三关重新回到get请求,会发现输入单引号报错,但是注释符…