前缀树介绍,定义,图文详解分析——Java/Kotlin双版本代码
创始人
2024-04-26 01:12:46
0

前缀树

前缀树,又称作字典树,用一个树状的数据结构储存字典中的所有单词。

列,一个包含can、cat、come、do、i、in、inn的前缀树如下图所示:

在这里插入图片描述

  • 前缀树是一个多叉树,一个节点可能存在多个节点。
  • 除根节点外,每个节点表示一个字符串的一个字符,整个字符串由前缀树的路径进行表示。
  • 字符串在前缀树的路径并不一定全部都是终止于叶节点,比如in对应的则是字符串inn的一部分。

前缀树的实现

接下来设计一颗前缀树PrefixTree,其包含如下的操作。

  1. insert,在前缀树中添加一个字符串。
  2. search,查找,如果该前缀树中存在该字符串,则返回true
  3. startWith,查找字符串前缀,如果前缀树中存在包含该字符串的前缀,则返回true,否则返回false
  4. matchingStartWith,查找所有包含该前缀的字符串,返回前缀树中所有包含该前缀的字符串,如果不存在则返回null

首先定义前缀树的数据结构,注意这里我们只考虑实现小写英文字母(具体可以根据业务逻辑调整),因为小写英文字母只有26个,所以我们可以将其放到一个容量为26的数组之中去。数组中第一个元素则是对应a的节点,第二个元素则是对应b的节点,依次往下。需要说明的是,不需要专门一个字段表示当前节点的字符,因为可以根据其在父节点对应的位置,从而得知对应的字符信息。

另外我们需要一个boolean类型的字段,去判断该节点的路径对应的字符串是否是一个完整的字符。

综上,数据结构可以定义为如下所示:

kotlin

class PrefixTree {private val root = Node()class Node {val childNode = Array(26) { null }var isWord = false}
}

java

    class PrefixTree {private Node root =new Node();class Node {Node[] childNode = new Node[26];boolean isWord = false;}}

insert函数实现

我们添加boybosshiboyhi四个单词,具体分析一下前缀树添加的过程:

  1. 添加boy,逐个添加字母boy对应的节点,并将最后一个字母y对应的节点的isWord标记为true
  2. 添加boss,此时前两个字母bo对应的节点之前已经创建出来,因此只需要创建两个对应s的节点,并将第2个s对应节点的字段isWord标记为true
  3. 添加hiboy,虽然之前有添加过boy三个单词,但是其并不是hiboy的前缀,所以需要为hiboy每个单词创建节点,并将最后的节点置为true
  4. 添加hi,由于hi为前缀,所以不需要创建节点添加,只需要将i对应的节点的isWord置为ture即可

在这里插入图片描述

所以,插入的代码可以做如下的实现

kotlin

    fun insert(word: String) {var localRoot = rootword.toCharArray().forEach { char ->val index = char - 'a'if (localRoot.childNode[index] == null) {localRoot.childNode[index] = Node()}localRoot = localRoot.childNode[index]!!}localRoot.isWord = true}

java

        public void insert(String world){Node localRoot = root;for (char c :world.toCharArray()){int index = c - 'a';if (localRoot.childNode[index]==null){localRoot.childNode[index] = new Node();}localRoot = localRoot.childNode[index]}localRoot.isWord = true;}

search函数实现

这个思考起来比较简单一点,直接从根节点开始查找,如果要查找的字符串对应的字符在根节点中不存在,则直接返回false,如果存在则前往该节点,在该节点查找是否存在与字符串对应的第二个字符的节点,没有返回false,如果存在则继续往下查找,直到查找完最后一个字符,最终判断如果isWordtrue则返回true,否则则返回false

所以代码如下所示:

kotlin

    fun search(word: String): Boolean {var localRoot = rootword.toCharArray().forEach { char: Char ->val index = char - 'a'if (localRoot.childNode[index] != null) {localRoot = localRoot.childNode[index]!!} else {return false}}return localRoot.isWord}

java

        public boolean search(String world){Node localRoot = root;for (char c :world.toCharArray()){int index = c - 'a';if (localRoot.childNode[index]!=null){localRoot = localRoot.childNode[index];}else {return false;}}return localRoot.isWord;}

startWith函数实现

函数startWithsearch不同,只要前缀树中存在以输入的前缀开头的单词就应该返回true。因此,函数startWith的返回值和函数search不同之外,其他代码是一样的。
kotlin

    fun startWith(word: String): Boolean {var localRoot = rootword.toCharArray().forEach { char: Char ->val index = char - 'a'if (localRoot.childNode[index] != null) {localRoot = localRoot.childNode[index]!!} else {return false}}return true}

java

        public boolean startWith(String world){Node localRoot = root;for (char c :world.toCharArray()){int index = c - 'a';if (localRoot.childNode[index]!=null){localRoot = localRoot.childNode[index];}else {return false;}}return true;}

matchingStartWith函数实现

该函数要求返回所有匹配到前缀的单词。

所以分为以下两个步骤:

  1. 匹配前缀,如果匹配不到直接返回null
  2. 匹配到之后,在该前缀的节点进行深度优先搜索,将遍历到的所有单词全部加入集合进行返回

所以代码如下所示:
kotlin

    fun matchingStartWith(word: String): List? {val wordResultPre = StringBuilder()var localRoot = rootword.toCharArray().forEach { char: Char ->val index = char - 'a'if (localRoot.childNode[index] != null) {wordResultPre.append(char)localRoot = localRoot.childNode[index]!!} else {return null}}//深度优先搜索 所有的剩余单词val result = ArrayList()dfs(localRoot, StringBuilder(),wordResultPre,result)return result}private fun dfs(node: Node, str: StringBuilder, wordResultPre: StringBuilder, result: ArrayList) {val childNodes = node.childNodefor (index in childNodes.indices) {val childNode = childNodes[index]if (childNode != null) {str.append(('a' + index).toChar())if (childNode.isWord) {result.add(wordResultPre.toString() + str.toString())}dfs(childNode,str, wordResultPre, result)}}}

java

        public List matchingStartWith(String world){StringBuilder wordResultPre = new StringBuilder();Node localRoot = root;for (char c :world.toCharArray()){int index = c - 'a';if (localRoot.childNode[index]!=null){wordResultPre.append(c);localRoot = localRoot.childNode[index];}else {return null;}}//深度优先搜索 所有的剩余单词List result =new ArrayList<>();dfs(localRoot,new StringBuilder(),wordResultPre,result);return result;}private void dfs(Node node, StringBuilder stringBuilder, StringBuilder wordResultPre, List result) {Node[] childNodes = node.childNode;for (int i =0 ;iNode childNode = childNodes[i];if (childNode!=null){stringBuilder.append('a'+i);if (childNode.isWord){result.add(wordResultPre.toString()+stringBuilder.toString());}dfs(childNode,stringBuilder,wordResultPre,result);}}}

前缀树应用

题目

输入一个包含n个单词的数组,可以把它们编码成一个字符串和n个下标。例如,单词数组["time","me","bell"]可以编码成一个字符串"time#bell#",然后这些单词就可以通过下标[0,2,5]得到。对于每个下标,都可以从编码得到的字符串中相应的位置开始扫描,直到遇到’#'字符前所经过的子字符串为单词数组中的一个单词。所以如果输入的是字符串数组["time","me","bell"],那么编码之后最短的字符串是"time#bell#",长度是10

分析

题目的目标是得到最短的编码,因此,如果一个单词是另一个单词的后缀,那么单词在编码字符串中就不需要单独出现,这是因为单词可以通过在单词中偏移下标得到。

所以我们很容易想到前缀树,但是题目是关于字符串的后缀。所以,我们可以反转字符串,之后使用前缀树。

根据题目信息,我们不需要关心每个单词,只需要遍历每个叶子节点对应的字符串的长度,然后加在一起即可。但是注意,字符串和字符串之间存在#,所以需要对长度进行额外+1。

总体来说使用深度优先搜索,代码参考如下:

    public void minLength(String [] words){PrefixTree.Node node = build(words);int [] total  = {0};dfs(node,1,total);}private void dfs(PrefixTree.Node node, int length, int[] total) {boolean isLeaf = true;for (PrefixTree.Node childNode : node.getChildNode()) {if (childNode != null) {isLeaf = false;dfs(childNode, length + 1, total);}}if (isLeaf) {total[0] += length;}}

🙆‍♀️。欢迎技术探讨噢!

相关内容

热门资讯

安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...
一加系统安卓降级,轻松还原经典... 你有没有想过,你的手机系统升级后,突然发现某些功能变得不那么顺心了?别急,今天就来聊聊一加系统安卓降...
日本最好的安卓系统,体验非凡 亲爱的读者们,你是否曾想过,在遥远的东方,有一个国家,他们的智能手机系统独具特色,让人眼前一亮?没错...
荣耀安卓11 系统证书,保障安... 你知道吗?最近手机圈里可是炸开了锅,荣耀安卓11系统证书成了大家热议的话题。这不,我就迫不及待地来和...
安卓手机开机升级系统,体验流畅... 你有没有发现,每次你的安卓手机开机,总会有那么一刹那,屏幕上跳出一个升级系统的提示?是不是觉得这就像...
真正的安卓系统手机,安卓系统手... 你有没有想过,为什么有些人对安卓系统手机情有独钟?是不是觉得市面上的安卓手机千篇一律,缺乏个性?别急...
安卓怎么用定位系统,轻松实现精... 你有没有想过,手机里的定位系统竟然这么神奇?它不仅能帮你找到回家的路,还能在茫茫人海中找到你的好友。...
安卓的哪个系统流畅,探索新一代... 你有没有想过,为什么你的安卓手机有时候像蜗牛一样慢吞吞的,而别人的手机却像风一样快?今天,就让我带你...
安卓系统解锁工具下载,畅享自由 你是不是也和我一样,对安卓系统的解锁工具感兴趣呢?想象你的手机被锁住了,无论是忘记密码还是想尝试新的...
谷歌退出安卓系统停用,停用背后... 你知道吗?最近有个大新闻在科技圈里炸开了锅!谷歌竟然宣布要退出安卓系统,这可真是让人大跌眼镜啊!想象...
安卓系统卡顿修复,轻松提升手机... 手机用久了是不是感觉有点卡卡的呢?别急,今天就来给你支几招,让你的安卓手机重焕生机,告别卡顿的烦恼!...
安卓系统停用怎么解除,轻松恢复... 你是不是也遇到了安卓系统停用的问题,急得像热锅上的蚂蚁?别急,今天就来给你详细解析怎么解除这个让人头...
最初始的安卓系统,技术演进与产... 亲爱的读者,你是否曾好奇过,那个如今无处不在的安卓系统,它的诞生之初是怎样的呢?今天,就让我们一起穿...
patchwall系统和安卓系... 你有没有发现,手机上的界面越来越个性化了?没错,这就是科技的魅力所在。今天,咱们就来聊聊两个在个性化...
汽车安卓系统换主题,焕新视觉体... 你有没有发现,汽车里的安卓系统换主题,简直就像给爱车换了个新衣裳,瞬间感觉焕然一新呢!想象当你驾驶着...
掌柜智囊收银系统安卓,高效便捷... 你有没有想过,在繁忙的店铺里,如何让收银工作既高效又轻松呢?今天,就让我带你一探究竟,看看这款掌柜智...
怎么控制安卓系统内存,安卓系统... 手机用久了是不是感觉越来越卡?别急,今天就来教你怎么控制安卓系统的内存,让你的手机重新焕发活力!一、...
电视机系统安卓系统吗,探索智能... 亲爱的读者,你是不是也和我一样,对家里的电视机系统充满了好奇?尤其是当它运行的是安卓系统时,那种探索...
魅族系统flyme安卓,魅族安... 你有没有发现,手机的世界里,总有一些品牌能让人眼前一亮?今天,咱们就来聊聊魅族旗下的Flyme系统,...
安卓仿ios系统链接,带你领略... 你有没有发现,最近安卓手机界掀起了一股仿iOS系统链接的热潮?这可不是什么小打小闹,而是各大厂商纷纷...