当前位置: 首页 > ops >正文

Leetcode百题斩-字典树

208. Implement Trie (Prefix Tree)[medium]

做完了哈希,来看看数据结构,做做字典树。字典树在搜索方面的作用还是蛮大的,主要是能实现前缀联想以及正确性匹配相关的功能。

字典树又名前缀树,顾名思义就是维护字符串的前缀。这个数据结构难度不大,除了根节点外,每个节点维护当前字符串当前字符的后一个可能出现的字符集合,即每个节点对应了一堆字符串公共前缀,由于字母一共只有26个,因此可以用一个26位的递归数组来表示,下一个字母对应的前缀。然后再加一个字段用来区分当前节点是否为字符串结尾。

该数据结构仅做了解,并且在前缀相关操作时注意进行应用,其可以在 O(n) 的复杂度下完成搜索插入以及前缀匹配等各种操作

class Trie {private Boolean isEnd;private Trie[] children;public Trie() {isEnd = false;children = new Trie[26];}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {return this.searchTree(word, true);}public boolean startsWith(String prefix) {return this.searchTree(prefix, false);}private boolean searchTree(String prefix, boolean needEnd) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return false;}node = node.children[index];}return needEnd ?  node.isEnd : true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

http://www.xdnf.cn/news/7634.html

相关文章:

  • MySQL 安全更新大量数据
  • MySQL高可用之ProxySQL + MGR 实现读写分离实战
  • 面向AI研究的模块化即插即用架构综述与资源整理全覆盖
  • 数据库实验——备份与恢复
  • 【普及−】洛谷P1862 ——输油管道问题
  • 【latex】文本颜色修改
  • 【QT】QTableWidget获取width为100,与真实值不符问题解决
  • C++ 网络编程(9)字节序处理和消息队列的控制
  • 缺乏进度跟踪机制,如何掌握项目状态?
  • MyBatis常用方法
  • 零售EDI:Belk Stores EDI需求分析
  • 阅读笔记---城市计算中用于预测学习的时空图神经网络研究综述
  • 《从零开始构建高可用MySQL架构:全流程实战指南》
  • 无人机避障——深蓝学院浙大Fast-planner学习部分(轨迹生成B-Spline部分)
  • Spring是如何实现scope作用域支持
  • 家用和类似用途电器的安全 第1部分:通用要求 与2005版差异(6)
  • pmap中的mode列,脏页,写时复制
  • 公路水运安全员C证用途及重要性
  • 测试工程师要如何开展单元测试
  • JavaSenderMail发送邮件(QQ及OFFICE365)
  • 如何使用通义灵码玩转Python - AI编程助手提升效率
  • 【工具变量】地级市健康城市试点政策数据集(2007-2024年)
  • 香港科技大学广州香港科技大学硕博士研究生学位项目宣讲会(智能制造硕博士物理学硕士)—深圳大学专场
  • 大模型从基础到入门 记录
  • 测试W5500的第3步_使用ioLibrary库创建TCPServer
  • [特殊字符] jQuery 响应式瀑布流布局插件推荐!
  • 2025年JIII SCI1区TOP,多策略霜冰优化算法IRIME+无人机路径规划,深度解析+性能实测
  • [创业之路-370]:企业战略管理案例分析-10-战略制定-差距分析的案例之小米
  • AI大模型从0到1记录学习 大模型技术之数学基础 day26
  • AR0144CSSC20SUKA0-CRBR——1/4英寸 1.0 MP 高性能CMOS图像传感器解析