Implement Trie (Prefix Tree)前缀树系列

2023-10-26

208. Implement Trie (Prefix Tree)  

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tree = []
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        self.tree.append(word)
        
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        return word in self.tree
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        for item in self.tree:
            if item.startswith(prefix):
                return True
        return False
            

648. Replace Words

class Solution:
    def replaceWords(self, roots: List[str], sentence: str) -> str:
        new_dic = {}
        for root in roots:
            length = len(root)
            new_dic[root] = length
        new_dic = sorted(new_dic.keys())
        sentence = sentence.split()
        new_sentence = sentence.copy()
        for root in new_dic:
            for i  in range(len(sentence)):
                if sentence[i][:len(root)] == root:
                    sentence[i] = "1"
                    new_sentence[i] = root
        output = ""
        for word in new_sentence:
            output  = output + " " + word
                  
        return output.lstrip()

 

 676. Implement Magic Dictionary  这个题可能是我AC的最好的一个题了 

Runtime: 20 ms, faster than 99.81% of Python3 online submissions for Implement Magic Dictionary.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Implement Magic Dictionary.

class MagicDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.roots = []
        

    def buildDict(self, root: List[str]) -> None:
        """
        Build a dictionary through a list of words
        """
        self.roots += root
        
        

    def search(self, word: str) -> bool:
        """
        Returns if there is any word in the trie that equals to the given word after modifying exactly one character
        """
        res = [0]
        for root in self.roots:
            if len(root) == len(word):
                temp = 0
                for i in range(len(root)):
                    if root[i] != word[i]:
                        temp +=1
                res.append(temp)
        if len(res) == 1:
            return False
        if 1 in res :
            return True
        else:
            return False
                        

 

677. Map Sum Pairs 这个题AC的效果也比较好

Runtime: 32 ms, faster than 92.23% of Python3 online submissions for Map Sum Pairs.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Map Sum Pairs.

class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = {}
        

    def insert(self, key: str, val: int) -> None:
        self.dic[key] = val
        

    def sum(self, prefix: str) -> int:
        res = 0
        for key in self.dic.keys():
            if key.startswith(prefix):
                res += self.dic[key]
                
        return res

 

 

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Implement Trie (Prefix Tree)前缀树系列 的相关文章

  • 计算机组成原理:奇偶校验和汉明码校验

    目录 一 奇偶校验 奇偶校验的规律及原理 二 汉明校验码 1 校验位位置 2 汉明码的位号实质上是参与校验的各校验位位号之和 3 计算校验位的值 4 校验 设置指错字 一 奇偶校验 了解汉明码校验之前需要知道奇偶校验 奇偶校验码是一种最简单
  • JS翻转数组

    js翻转数组 reverse 方法翻转 反向添加数组 数组首尾交换 unshift 向数组头部添加 考点 在 数组首尾交换 reverse 方法肯定不是 reverse 是js方法 反向添加数组 和 unshift 向数组头部添加元素 创建
  • Java多线程学习(吐血超详细总结)

    写在前面的话 此文只能说是java多线程的一个入门 其实Java里头线程完全可以写一本书了 但是如果最基本的你都学掌握好 又怎么能更上一个台阶呢 如果你觉得此文很简单 那推荐你看看Java并发包的的线程池 Java并发编程与技术内幕 线程池
  • 基于springboot、uniapp的智慧物联网系统

    一 项目简介 基于springboot uniapp的智慧物联网系统 二 实现功能 支持二开智能家居系统 支持智慧办公系统 支持智慧社区系统 支持农业监测系统 支持水利监测系统 支持工业控制系统 三 技术选型 springboot unia
  • c++11并发与多线程-王健伟-专题视频课程

    c 11并发与多线程 364人已学习 课程介绍 本课程 讲解的重点定位在c 11新标准中的多线程开发部分 同时 老师还会结合自己的经验把多线程的讲解进一步拓展到一个比较大的范畴 因为无论是c 11多线程开发还是各种其他的多线程开发实现方法
  • Kali Linux入门教程(非常详细)从零基础入门到精通,看完这一篇就够了。

    作为一名从事渗透测试的人员 不懂Kali Linux的话 就out了 它预装了数百种享誉盛名的渗透工具 使你可以更轻松地测试 破解以及进行与数字取证相关的任何其他工作 今天给大家分享一套Kali Linux资料合集 包括12份Kali Li
  • FreeAnchor: Learning to Match Anchors for Visual Object Detection阅读

    摘要 现在基于CNN的算法都是使用IOU对目标分配Anchor 我们提出一种方法打破了IOU的限制 允许自由的分配Anchor 我们的方法 称为自由锚 FreeAnchor 将手工锚分配升级为 自由 锚匹配 FreeAnchor的目标是学习

随机推荐

  • JavaWeb之前后端分离的三步骤

    文章目录 一 Ajax 异步JavaScript和XML 1 1 Ajax 发送请求的步骤 1 2 如果是POST请求 则还需要设置请求头 二 JSON的使用 2 1 概念 2 2 格式 2 3 JSON 和 JS 转换 2 4 JSON
  • 返回值优化

    返回值优化 在以下几种情况中 编译器可能会省略对象的拷贝和移动操作 对象直接在原本拷贝 移动的内存中直接构造对象 当发生这种优化时 虽然拷贝 移动构造函数没有调用 但是拷贝 移动构造函数必须是可访问的 否则程序是错误的 在return语句中
  • python+Excel系列:数据导入和整理模块—pandas

    文章目录 数据导入和整理模块 pandas 一 初识pandas模块 二 二维数据表格DataFrame的创建与索引的修改 1 DataFrame的创建 1 通过列表创建DataFrame 2 通过字典创建DataFrame 3 通过二维数
  • Python requests请求方法封装

    一种对requests各种请求方法的封装 提高使用效率 特别注意的是data格式 具体业务具体分析 有的是json格式 直接上代码吧 usr bin env python coding utf 8 Author Jianhua Wang S
  • IDEA常用的配置

    1 主题风格 有些小伙伴不太喜欢黑色主题 此时可以设置IDEA的主题风格 Settings gt Editor gt Color Scheme 2 设置字体 假如一个方法有50 60行 字体设置过大 要看完整个方法 需要滚动多次滑轮 由于字
  • JVM底层又是如何实现synchronized的

    目前在Java中存在两种锁机制 synchronized和Lock Lock接口及其实现类是JDK5增加的内容 其作者是大名鼎鼎的并发专家Doug Lea 本文并不比较synchronized与Lock孰优孰劣 只是介绍二者的实现原理 数据
  • cuda与Eigen不兼容的解决方案

    cuda提供强大的矩阵计算库cuBlas 但cuBlas没法进行特征值 逆矩阵等高级的运算 要解决这个问题 要么自己写算法 太难 要么调用线性代数运算库 而线性代数运算库中Eigen是最简便易用的一个 当我想把这两个库放在一起编译的时候 出
  • 因果推断(一)-基础

    1 因果推断定义 根源 因果推断就是找到事情发生的原因 重要的现象 桑普森悖论 Casualty和Association之间的区别 Association是人工智能的基础 人工智能Association的问题 知其然 不知其所以然 不可解释
  • System.out.println()的详细解释

    System out println 的深入理解 文章参考了公众号 Java面试那些事儿 面向对象编程即创建了对象 所有的事情让对象帮忙操作 即对象调用方法 System out println hello world 输出 hello w
  • ubuntu 进入 recovery mode 修改系统文件

    当ubuntu无法启动时 根据提示修改某些配置即可 无需重新安装系统 recovery mode 为我们提供了这种便利 启动步骤如下 1 recovery mode 按e键进入如下菜单 2 ro recovery nomodeset 修改为
  • 文件夹重定向失败解决方案

    系统 Win7 原本想将Administrator里的下载目录重定向到D盘下的Download 结果目标选择了D盘 再想将其改成D Download时 出现 无法将父级重定向到后代 指定的路径无效 的提示 想恢复成默认 系统又说 无法生成
  • 2021美赛C题数据(完整有解压密码)

    C题数据 数据链接 https pan baidu com s 1ahACnhdNWRbfRQSVqPM eQ 提取码 eatx 解压的密码是 Af6SP7rdm33PxPJmDb4wZq7cw 说实话 一看到数据 我就果断放弃了C 不过肯
  • CPU的两种架构概要

    2种CPU架构 冯诺伊曼架构和哈佛架构 1 哈佛结构 是一种将程序指令储存 和 数据储存分开的存储器结构 哈佛结构的微处理器通常具有较高的执行效率 其程序指令和数据指令分开组织和储存的 执行时可以预先读取下一条指令 常见的有 PIC系列芯片
  • 计算机毕业设计ssm基于MySQL的房屋中介系统7m60a9 (附源码)轻松不求人

    项目运行 环境配置 Jdk1 8 Tomcat7 0 Mysql HBuilderX Webstorm也行 Eclispe IntelliJ IDEA Eclispe MyEclispe Sts都支持 项目技术 ssm mybatis Ma
  • VBS脚本统计红楼梦中贾宝玉出现的次数

    VBS脚本统计红楼梦中贾宝玉出现的次数 文件 链接 https pan baidu com s 1T XIbIHzMZiIX8IiSMcZdg 提取码 sti6 脚本代码 Dim fso ts s 创建Scripting FileSyste
  • 一份关于windows server服务器的安全漏洞处理建议(来自绿盟安全评估)

    文章目录 前言 一 服务器主机存在漏洞应该怎么修复 二 报告中的高危漏洞 部分展示 1 Microsoft Windows CredSSP 远程执行代码漏洞 CVE 2018 0886 2 SSL TLS协议信息泄露漏洞 CVE 2016
  • matlab读取csv有字符有数字,MATLAB读取csv文件里面既有文本又有数字的文件怎么读取。(可以不止csv文件,txt等文件都可以)...

    MATLAB读取csv文件里面既有文本又有数字的文件怎么读取 一 第一种方法用代码读取 用代码读取 1 如果你要读的文件里面都是数字的话 用csvread函数 它有三种方式读取 但是它的缺点就是只能读取全是数值的文件 简单来说 只能读数字
  • 智能小车红绿灯识别功能的实现(python,ubuntu)

    From sztu 自动化专业的小菜鸡 1 基本介绍 交通标志识别代码存在于 config teleop src smartcar scripts文件目录下的camera cmd py中 核心程序为light detection函数 lig
  • JavaScript实现简单区块链

    用JavaScript来实现一个简单的区块链 通过实现过程 你将理解区块链是什么 区块链就是一个分布式数据库 存储结构是一个不断增长的链表 链表中包含着许多有序的记录 然而 在通常情况下 当我们谈到区块链的时候也会谈起使用区块链来解决的问题
  • Implement Trie (Prefix Tree)前缀树系列

    208 Implement Trie Prefix Tree class Trie def init self Initialize your data structure here self tree def insert self wo