【Leetcode】二十一、前缀树 + 词典中最长的单词

文章目录

  • 1、背景
  • 2、前缀树Trie
  • 3、leetcode208:实现Trie
  • 4、leetcode720:词典中最长的单词

1、背景

在这里插入图片描述
如上,以浏览器搜索时的自动匹配为例:

在这里插入图片描述

如果把所有搜索关键字放一个数组里,则:插入、搜索一个词条时,时间复杂度为O(n),判断某个前缀是否存在,时间复杂度为O(n × m),m为词条长度,因为在遍历数组时,要挨个对比数组每个元素的每个字符和词条前缀的每个字符是否相同,得两层for循环,时间复杂度太高,比如在以下数组判断是否有前缀为haha的关键字:

[goog,googl,google,bai,baidu,gi]

2、前缀树Trie

前缀树,又叫字典树,是一种数据结构,Trie,发音类似 “try”。比如存以下这些数据到前缀树:

goog,googl,google,bai,baidu,gi

效果:

在这里插入图片描述

root节点,一般不存数据,其下有孩子节点。以goog为例,存到第二个g时,这个单词没了,此时,这儿所在的节点,会有一个结束的Flag,以及该Flag处对应的值。从以上的分析,大致可以看出,前缀树Trie这种结构,其对象应该有以下属性:

  • 孩子节点children
  • 某个单词的结束标志isEnd

关于时间复杂度,如果输入字符串str,其长度为k:

  • 插入:O(k)
  • 搜索:O(k)
  • 判断是否存在str这个前缀的词语:O(k)

关于前缀树这种结构的应用场景:

  • 前缀匹配
  • 词频统计(做统计,当然也可用HashMap实现)

3、leetcode208:实现Trie

以英语单词为例,26个字母,根据ASCII码转为数字,就是数组的下标。Trie类应该有个isEnd属性,因为要区分:

  • 是否有str这个单词
  • 是否有以str开头(为前缀)的单词

比较到str的最后一个字母,isEnd为true,说明有str这个单词,是否有这个前缀,则不用考虑isEnd。

此外,正常来说,每个Trie节点的值val也要存一下,但对英文字母不用,因为其对应的SSCII码,可以当下标,下标转一下就是字母值。

在这里插入图片描述

参照以上示意图,每个节点上存着一个字母(索引与ASCII码),写前缀树的实现:

public class Trie {private Trie[] children;private boolean isEnd;public Trie() {// 26个英文字母,每个节点最多26个儿子节点children = new Trie[26];isEnd = false;}public void insert(String word) {// 调用insert方法的对象,可认为是根节点Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);// 字母转ASCII码,a对应97,减去a,可让值从0开始,而不是97,方便对应数组下标int index = ch - 'a';if (node.children[index] == null) {// 这是个新字母,创建一个新的节点,作为子节点// 这个节点对应的字母的值不用存,下标+97转回去就是这个节点的值node.children[index] = new Trie();}// 该判断word里的下一个字母了,node节点不再是根节点,而是第一个字母的对应的节点node = node.children[index];}// 整个word都遍历完了,结束标志为置为truenode.isEnd = true;}public boolean search(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);// 字母转ASCII码,a对应97,减去a,可让值从0开始,而不是97,方便对应数组下标int index = ch - 'a'; if (node.children[index] == null) {// 往下顺,如果有字母不一样,说明一定不存在这个单词return false;}// 检查下一个字母,替换下Tire节点node = node.children[index];}// 和判断前缀是否存在不一样,搜索,找到末尾后,末尾这儿必须有单词的结束标志isEndreturn node.isEnd;}public boolean startsWith(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);// 字母转ASCII码,a对应97,减去a,可让值从0开始,而不是97,方便对应数组下标int index = ch - 'a';if (node.children[index] == null) {return false;}// 检查下一个字母,替换下Tire节点node = node.children[index];}return true;}
}

搜索和判断前缀的代码重复度太高,优化下,抽取公共代码

public class Trie {private Trie[] children;private boolean isEnd;public Trie() {// 26个英文字母,每个节点最多26个儿子节点children = new Trie[26];isEnd = false;}public void insert(String word) {// 调用insert方法的对象,可认为是根节点Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);// 字母转ASCII码,a对应97,减去a,可让值从0开始,而不是97,方便对应数组下标int index = ch - 'a';if (node.children[index] == null) {// 这是个新字母,创建一个新的节点,作为子节点// 这个节点对应的字母的值不用存,下标+97转回去就是这个节点的值node.children[index] = new Trie();}// 该判断word里的下一个字母了,node节点不再是根节点,而是第一个字母的对应的节点node = node.children[index];}// 整个word都遍历完了,结束标志为置为truenode.isEnd = true;}/*** 搜索和判断前缀是否存在,两个操作的公共逻辑抽取** @param str 输入的字符串* @return 返回最后一个字母对应的Trie节点,无则返回null*/public Trie getTrieNode(String str) {if (str == null) {return null;}// 调用insert方法的对象,可认为是根节点Trie node = this;for (int i = 0; i < str.length(); i++) {char ch = str.charAt(i);// 字母转ASCII码,a对应97,减去a,可让值从0开始,而不是97,方便对应数组下标int index = ch - 'a';if (node.children[index] == null) {// 往下顺,如果有字母不一样,说明一定不存在这个单词或前缀return null;}// 检查str的下一个字母,替换下Tire节点node = node.children[index];}return node;}public boolean search(String word) {Trie trieNode = getTrieNode(word);// 和判断前缀是否存在不一样,搜索,找到末尾后,末尾这儿必须有单词的结束标志isEndreturn trieNode != null && trieNode.isEnd;}public boolean startsWith(String prefix) {return getTrieNode(prefix) != null;}
}

从优化后的代码可以看到,搜索和判断前缀的区别是,判断到输入字符的最后一个字母后,搜索要有isEnd标志为true,表示有这样的单词,以免出现,搜abc,但只有abcd时也返回true的情况。而判断前缀是否存在,则不用考虑这个标志位。

4、leetcode720:词典中最长的单词

在这里插入图片描述
如题中示例1,能返回world,需要前面有w ⇒ wo ⇒ wor ⇒ worl这四个词语才行

在这里插入图片描述

将题中数组的每个单词存入前缀树,然后遍历数组。比如app单词,a字母找到了,且isEnd为true,往下ap,也找到了,且isEnd为true,如此app这个单词就是目前符合要求的。

public class P720 {public String longestWord(String[] words) {if (null == words || words.length == 0) {return "";}Trie trie = new Trie();for (String word : words) {trie.insert(word);}String result = "";// 控制精确跳到外层循环,而不是内层outerLoop:for (String word : words) {String temp = "";for (String s : word.split("")) {temp = temp + s;if (!trie.search(temp)) {// 如果有一个字母找不到,则直接看题中数组里的下一个单词continue outerLoop;}}// 判断完一个单词符号要求后,如果长度超过了result,则替换if (word.length() > result.length()) {result = word;} else if (word.length() == result.length()) {// 如果判断完一个单词符号要求后,如果长度等于result,则对比,取字典序小的// compareToIgnoreCase() 方法与 compareTo() 方法类似,但会忽略大小写result = word.compareToIgnoreCase(result) < 0 ? word : result;}}return result;}
}

以上,套用了208题的Trie类的search方法,search方法只判断搜到末尾时,isEnd是否为true,即它只关心有没有world这个词,而不关心有没有w ⇒ wo ⇒ wor ⇒ worl这四个词语(isEnd为true),再修改下search方法:

public class Trie {private Trie[] children;private boolean isEnd;//略,同上一题/*** 搜索是否有word单词,以及w ⇒ wo ⇒ wor ⇒ worl这四个单词*/public boolean searchByStep(String word) {if (word == null) {return false;}// 根节点Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';// 没有这个字母,或者这地方结束标志为false,则返回falseif (node.children[index] == null || !node.children[index].isEnd) {return false;}// 检查str的下一个字母,替换下Tire节点node = node.children[index];}// 到最后一个字母所在的节点了return node != null && node.isEnd;}
}

用新的前缀树搜索方法(判断word是否存在的同时,还要判断w ⇒ wo ⇒ wor ⇒ worl这四个是否存在),并简化下实现代码:

public class P720 {public String longestWord(String[] words) {if (null == words || words.length == 0) {return "";}Trie trie = new Trie();for (String word : words) {trie.insert(word);}String result = "";for (String word : words) {// 不符合条件,判断下一个单词if (!trie.searchByStep(word)) {continue;}// 判断完一个单词符合要求后,如果长度超过了result,则替换// 如果判断完一个单词符号要求后,如果长度等于result,则对比,取字典序小的替换result// compareToIgnoreCase() 方法与 compareTo() 方法类似,但会忽略大小写if (word.length() > result.length() || (word.length() == result.length()) && word.compareToIgnoreCase(result) < 0) {result = word;} }return result;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/379747.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VisualRules-Web案例展示(一)

VisualRules单机版以其卓越的功能深受用户喜爱。现在&#xff0c;我们进一步推出了VisualRules-Web在线版本&#xff0c;让您无需安装任何软件&#xff0c;即可在任何浏览器中轻松体验VisualRules的强大功能。无论是数据分析、规则管理还是自动化决策&#xff0c;VisualRules-W…

【深度学习】PyTorch框架(3):优化与初始化

1.引言 在本文中&#xff0c;我们将探讨神经网络的优化与初始化技术。随着神经网络深度的增加&#xff0c;我们会遇到多种挑战。最关键的是确保网络中梯度流动的稳定性&#xff0c;否则可能会遭遇梯度消失或梯度爆炸的问题。因此&#xff0c;我们将深入探讨以下两个核心概念&a…

VScode:前端项目中yarn包的安装和使用

一、首先打开PowerShell-管理员身份运行ISE 输入命令&#xff1a; set-ExecutionPolicy RemoteSigned 选择“全是”&#xff0c;表示允许在本地计算机上运行由本地用户创建的脚本&#xff0c;没有报错就行了 二、接着打开VScode集成终端&#xff0c;安装yarn插件 输入 npm ins…

活动回顾 | AutoMQ 联合 GreptimeDB 共同探讨新能源汽车数据基础设施

7 月 13 日&#xff0c;AutoMQ 携手 GreptimeDB“新能源汽车数据基础设施” 主题 meetup 在上海圆满落幕。本次论坛多角度探讨如何通过创新的数据管理和存储架构&#xff0c;提升汽车系统的性能、安全性和可靠性&#xff0c;从而驱动行业的持续发展和创新&#xff0c;涵盖 Auto…

全时守护,无死角监测:重点海域渔港视频AI智能监管方案

一、方案背景 随着海洋经济的快速发展和海洋资源的日益紧缺&#xff0c;对重点海域渔港进行有效监控和管理显得尤为重要。视频监控作为一种高效、实时的管理手段&#xff0c;已成为渔港管理中不可或缺的一部分。当前&#xff0c;我国海域面积广阔&#xff0c;渔港众多&#xf…

QT CNA上位机报错 解决方案

QT编译报错: -lControlCAN 解决方案 更换三个文件&#xff0c;即可解决(QT 自带的是32位库&#xff0c;应使用64位库文件)

docker desktop历史版本安装

1.安装choco Windows安装 choco包管理工具-CSDN博客 2.通过choco安装 下面例子为安装旧版2.3.0.2,其它版本类似 Chocolatey Software | Docker Desktop 2.3.0.2 https://download.docker.com/win/stable/45183/Docker%20Desktop%20Installer.exe choco install docker-des…

【postgresql】pg_dump备份数据库

pg_dump 介绍 pg_dump 是一个用于备份 PostgreSQL 数据库的实用工具。它可以将数据库的内容导出为一个 SQL 脚本文件或其他格式的文件&#xff0c;以便在需要时进行恢复或迁移。 基本用法 pg_dump [选项] [数据库名] 命令选项 -h 或 --host&#xff1a;指定数据库服务器的主…

跟着操作,解决iPhone怎么清理内存难题

在如今智能手机功能日益强大的时代&#xff0c;我们使用手机拍照、录制视频、下载应用、存储文件等操作都会占用手机内存。当内存空间不足时&#xff0c;手机运行会变得缓慢&#xff0c;甚至出现卡顿、闪退等现象。因此&#xff0c;定期清理iPhone内存是非常必要的。那么&#…

力扣第十七题——电话号码的字母组合

内容介绍 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits "23" 输出…

iredmail服务器安装步骤详解!如何做配置?

iredmail服务器安全性设置指南&#xff1f;怎么升级邮件服务器&#xff1f; iredmail是一个功能强大的邮件服务器解决方案&#xff0c;它集成了多个开源软件&#xff0c;使您能够快速部署和管理邮件服务。AokSend将逐步引导您完成安装过程&#xff0c;无需深入的编程知识即可轻…

【ai】学习笔记:电影推荐1:协同过滤 TF-DF 余弦相似性

2020年之前都是用协同过滤2020年以后用深度学习、人工智能视频收费的,不完整,里面是电影推荐 这里有个视频讲解2016年大神分析了电影推荐 :MovieRecommendation github地址 看起来是基于用户的相似性和物品的相似性,向用户推荐物品: 大神的介绍: 大神的介绍: 基于Pytho…

海外营销推广:快速创建维基百科(wiki)词条-大舍传媒

一、维基百科的永久留存问题 许多企业和个人关心维基百科是否能永久留存。实际上&#xff0c;只要企业和个人的行为没有引起维基百科管理方的反感&#xff0c;词条就可以长期保存。如果有恶意行为或被投诉&#xff0c;维基百科可能会对词条进行删除或修改。 二、创建维基百科…

Python项目打包与依赖管理指南

在Python开发中&#xff0c;python文件需要在安装有python解释器的计算机的电脑上才能运行&#xff0c;但是在工作时&#xff0c;我们需要给客户介绍演示项目功能时并不一定可以条件安装解释器&#xff0c;而且这样做非常不方便。这时候我们可以打包项目&#xff0c;用于给客户…

平价养猫必看!测评几十款选出的最值得入手的希喂主食冻干

各位铲屎官&#xff0c;今天来聊聊我近期发现的宝藏主食冻干——希喂CPMR2.0大橙罐。平价养猫必看&#xff01;&#xff0c;在追求猫咪饮食健康与自身预算平衡的路上&#xff0c;我尝试了多种产品&#xff0c;而希喂以其高含肉量和高营养价值脱颖而出。它让喂食变得多样化且高效…

【STM32】LED闪烁LED流水灯蜂鸣器(江科大)

LED正极&#xff1a;外部长脚、内部较小 LED负极&#xff1a;外部短脚、内部较大 LED电路 限流电阻&#xff1a;保护LED&#xff0c;调节LED亮度&#xff08;本实验用面包板为了方便&#xff0c;省去了限流电阻&#xff0c;设计电路时要加上&#xff09; 左上图&#xff1a;低…

【golang-ent】go-zero框架 整合 ent orm框架 | 解决left join未关联报错的问题

一、场景 1、子表&#xff1a;cp_member_point_history cp_member_point_history表中字段&#xff1a;cp_point_reward_id 是cp_point_reward的主键id 当本表中的cp_point_reward_id字段为0&#xff08;即&#xff1a;没有可关联主表的&#xff09; CREATE TABLE cp_member_poi…

“社群+”生态下的开源AI智能名片源码:驱动商业与社会连接的新引擎

摘要&#xff1a;在“社群”生态日益成为主流趋势的今天&#xff0c;开源AI智能名片源码作为技术创新与社群运营的深度融合体&#xff0c;正逐步展现出其重塑商业格局、深化社会连接的巨大潜力。本文旨在深入探讨开源AI智能名片源码的技术特性、在“社群”生态中的具体应用、对…

Java线程池ThreadPoolExecutor原理、源码分析

目录 为什么要使用线程池&#xff1f; 线程池执行任务的具体流程是怎样的&#xff1f; 线程池的五种状态是如何流转的&#xff1f; 线程池中的线程是如何关闭的&#xff1f; 线程池为什么一定得是阻塞队列&#xff1f; 线程发生异常&#xff0c;会被移出线程池吗&#xff…

【产品那些事】固件安全-关于OTA升级包分析

文章目录 前言什么是OTA?升级包(固件)的类型和架构案例tp-link路由器升级包怎么解包分析?binwalk安装及使用ubi_reader安装及使用unsquashfs安装及使用某车企OTA升级包通用Android OTA解包相关分区第二层解包前言 什么是OTA? OTA(Over-the-Air)是一种通过无线通信网络(…