【LeetCode-中等题】208. 实现 Trie (前缀树)

文章目录

    • 题目
    • 方法一:利用数组构建26叉树
    • 方法二:利用哈希表构建26叉树

题目

在这里插入图片描述

方法一:利用数组构建26叉树

插入图示:
在这里插入图片描述
全搜索和前缀搜索:
注意:全局匹配匹配完直接返回插入时的标志位
而前缀匹配时,匹配成功后直接返回true 因为不需要往下匹配了

匹配到空trie都统统直接返回false
在这里插入图片描述

// 方法一  : 利用数组存储孩子节点private Trie[] children ; //孩子数组  private boolean isWord ; //标志位public Trie() {//构造函数children = new Trie[26];// 初始化为大小为26的数组isWord = false;//标志位初始化为false}//插入操作public void insert(String word) {Trie root  = this;//给祖先节点赋空对象//此时 孩子数组为空  标志位默认falsefor(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标char ch = word.charAt(i);int idx = ch - 'a';if(root.children[idx] == null){  //如果发现当前位置 为null  则是第一次插入,创建新的trieroot.children[idx] = new Trie();}root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层}root.isWord = true;  //插入完成  标记为true}//全匹配操作public boolean search(String word) {Trie root  = this;//获得当前对象for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标char ch = word.charAt(i);int idx = ch - 'a';if(root.children[idx] == null){  //如果发现当前位置 为null  说明搜索不到  直接return faslereturn false;}root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层继续搜索}return root.isWord;//如果能搜索到 则直接就是返回本来的状态值}// 前缀匹配public boolean startsWith(String prefix) {Trie root  = this;//获得当前对象for(int i = 0 ; i<prefix.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标`在这里插入代码片`char ch = prefix.charAt(i);int idx = ch - 'a';if(root.children[idx] == null){  //如果发现当前位置 为null  说明搜索不到  直接return faslereturn false;}root = root.children[idx]; //如果当前位置存在,那么将指针指向下一层继续搜索}return true;//如果能搜索到 则直接就是返回true}

方法二:利用哈希表构建26叉树

相比较上面的用数组构建26叉树,其实也可以采用哈希表存储子节点

在这里插入图片描述

方法二  : 利用hashmap存储孩子节点private Map<Character,Trie> children ; //孩子哈希表  key 为父节点  value为子trie节点  private boolean isWord ; //标志位public Trie() {//构造函数children = new HashMap<>();// 初始化哈希表isWord = false;//标志位初始化为false}//插入操作public void insert(String word) {Trie root  = this;//给祖先节点赋空对象for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标char ch = word.charAt(i);Trie node = root.children.get(ch);if(node == null){  //如果发现当前位置 为null  则是第一次插入,创建新的trieroot.children.put(ch,new Trie());}root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层}root.isWord = true;  //插入完成  标记为true}//全匹配操作public boolean search(String word) {Trie root  = this;//获得当前对象for(int i = 0 ; i<word.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标char ch = word.charAt(i);Trie node = root.children.get(ch);if(node == null){  //如果发现当前位置 为null  说明搜索不到  直接return faslereturn false;}root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层继续搜索}return root.isWord;//如果能搜索到 则直接就是返回本来的状态值}// 前缀匹配public boolean startsWith(String prefix) {Trie root  = this;//获得当前对象for(int i = 0 ; i<prefix.length() ; i++){//一个一个拆分字符串,将字符 - 'a' 转换为坐标char ch = prefix.charAt(i);Trie node = root.children.get(ch);if(node == null){  //如果发现当前位置 为null  说明搜索不到  直接return faslereturn false;}root = root.children.get(ch); //如果当前位置存在,那么将指针指向下一层继续搜索}return true;//如果能搜索到 则直接就是返回true}

参考:Leetcode 208 实现Trie(前缀树)

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

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

相关文章

软考(1)-面向对象的概念

目录 一. 软考基本信息 1. 软考时间&#xff1a; 2. 软考科目&#xff1a; 3.专业知识介绍 -- 综合知识考点分布 4. 专业介绍 -- 软件设计考点分布 二. 面向对象概念 1. 封装 考点一&#xff1a;对象 考点二&#xff1a;封装private 2. 继承 考点三&#xff1a;类 考…

React中父子组件参数传递讲解

文章目录 结合案例&#xff1a;github搜索案例1.父容器代码2.搜索Search子模块代码3.展示Lisi子模块代码 父子参数传递分析1.子(Search)传父(App)2.父(App)传子(List) 结合案例&#xff1a;github搜索案例 案例结果展示如下图 1.父容器代码 import React, { Component } fr…

【MySQL学习笔记】(十)使用索引的操作

简单使用索引 创建索引创建主键索引创建唯一键索引普通索引的创建 查询索引删除索引索引创建原则 数据库中的索引与书籍中的索引类似&#xff0c;在一本书中&#xff0c;利用索引可以快速地查找所需信息&#xff0c; 而无须阅读整本书。在数据库中&#xff0c;索引使数据库程序…

伯俊ERP与金蝶云星空对接集成表头表体组合查询连通分布式调出单新增(调拨出库对接分布式调出(KD调拨)6月)

伯俊ERP与金蝶云星空对接集成表头表体组合查询连通分布式调出单新增(调拨出库对接分布式调出&#xff08;KD调拨&#xff09;6月) 对接系统&#xff1a;伯俊ERP 伯俊科技&#xff0c;依托在企业信息化建设方面的领先技术与实践积累&#xff0c;致力于帮助企业实现全渠道一盘货。…

Git常用命令用法

参考视频&#xff1a;真的是全能保姆 git、github 保姆级教程入门&#xff0c;工作和协作必备技术&#xff0c;github提交pr - pull request_哔哩哔哩_bilibili 1.Git初始化 首先设置名称和邮箱。然后初始化一下&#xff0c;然后就创建了一个空的Git仓库。 PS D:\golang\oth…

【Linux】地址空间概念

目录 前言&#xff1a; 地址空间回顾 验证&#xff1a;一个变量是否会有两个值&#xff1f; 一. 什么是地址空间 虚拟地址与物理地址之间的关系 二. 地址空间是如何设计的 1. 回答一个变量两个值 2.扩展 继续深入理解 三. 为什么要有地址空间 原因&#xff1a; 1. 使…

【探索Linux】—— 强大的命令行工具 P.7(进程 · 进程的概念)

阅读导航 前言一、冯诺依曼体系结构二、操作系统&#xff08;OS&#xff09;1. 概念 三、进程1. 进程的概念2. PCB&#xff08;Process Control Block&#xff09;3. 查看进程 四、fork函数1. 函数简介2. 调用方式3. 返回值4. 使用示例 五、进程的几种状态1. 状态简介2. 进程状…

react中使用cytoscape

1. 安装 cytoscape npm install cytoscape 2. 使用 import React, { useEffect, useRef, useState } from "react"; import cytoscape from "cytoscape";const peopleList [{"data": {"id": "1","label": &qu…

三步搭建个人网站并发布上线【内网穿透】

三步搭建个人网站并发布上线【内网穿透】 文章目录 三步搭建个人网站并发布上线【内网穿透】前言一、在本地电脑上制作一个网站二、使用WordPress建立网站三、通过cpolar建立的数据隧道发布到公网上 前言 在这个个性飞扬的时代&#xff0c;每个人都希望拥有表现自我的平台&…

git快速使用

1、下载git 设置签名 2、基本概念 工作区&#xff1a;写代码的地方。 暂存区&#xff1a;.git的.index 工作区&#xff1a;.git 3、常用操作 本地codinggit init&#xff0c; 初始化一个本地仓库&#xff0c;项目根目录下会出现个.gitgit remote add origin gitgithub.com…

Git的基本使用笔记——狂神说

版本控制 版本迭代&#xff0c; 版本控制( Revision control)是一种在开发的过程中用于管理我们对文件、目录或工程等内容的修改历史&#xff0c;方便查看更改历史记录&#xff0c;备份以便恢复以前的版本的软件工程技术。 实现跨区域多人协同开发 追踪和记载一个或者多个文件的…

网络类型+二层封装技术

一、网络类型分类 1、点到点网络 在一个网段中&#xff0c;只能部署两个节点&#xff08;两个IP&#xff09;&#xff0c;如GRE环境就属于虚拟的点到点网络类型&#xff0c;通常是串线连接。 如下图当前只存在两个节点&#xff0c;但并不是点到点&#xff0c;因为它中间网段…

SAP message-06 027 供应商 还未为采购组织 创建

目录 错误信息 一、错误原因 二、修正 错误信息 When creating a RFQ in ME41 for a vendor that is not assigned to the Purchasing Organization, error "Vendor & has not been created for purch. organization" is not raised. Supplier AEQI1 has not be…

css之层叠上下文

之前调元素的显示优先级时&#xff0c;只会默默的调z-index以达到效果&#xff0c;但有时不生效&#xff0c;又不知道根因。刚好详细了解到层叠上下文&#xff0c;可以解释此类问题。 什么是层叠上下文&#xff1f; 在CSS2.1规范中&#xff0c;每个盒模型的位置是三维的&…

SpringMVC_SSM整合

一、回顾SpringMVC访问接口流程 1.容器加载分析 容器分析 手动注册WebApplicationContext public class ServletConfig extends AbstractDispatcherServletInitializer {Overrideprotected WebApplicationContext createServletApplicationContext() {//获取SpringMVC容器An…

Spark 6:Spark SQL DataFrame

SparkSQL 是Spark的一个模块, 用于处理海量结构化数据。 SparkSQL是用于处理大规模结构化数据的计算引擎 SparkSQL在企业中广泛使用&#xff0c;并性能极好 SparkSQL&#xff1a;使用简单、API统一、兼容HIVE、支持标准化JDBC和ODBC连接 SparkSQL 2014年正式发布&#xff0c;当…

使用webdriver-manager解决浏览器与驱动不匹配所带来自动化无法执行的问题

1、前言 在我们使用 Selenium 进行 UI 自动化测试时&#xff0c;常常会因为浏览器驱动与浏览器版本不匹配&#xff0c;而导致自动化测试无法执行&#xff0c;需要手动去下载对应的驱动版本&#xff0c;并替换原有的驱动&#xff0c;可能还会遇到跨操作系统进行测试的时候&…

LeetCode(力扣)17. 电话号码的字母组合Python

LeetCode17. 电话号码的字母组合 题目链接代码 题目链接 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/ 代码 class Solution:def __init__(self):self.letterMap ["", # 0"", # 1"abc", # 2"def&qu…

aop中获取@PathVariable参数

1.controller中的声明 2.aop中获取 RequestAttributes attributes RequestContextHolder.getRequestAttributes(); ServletRequestAttributes servletRequestAttributes (ServletRequestAttributes)attributes; HttpServletRequest request servletRequestAttributes.getReq…

深圳-海岸城购物中心数据分析

做数据分析的时候&#xff0c;如果要对商场进行分析&#xff0c;可以从这些数据纬度进行分析&#xff0c;如下图所示&#xff1a; 截图来源于数位观察&#xff1a;https://www.swguancha.com/