【python】Leetcode每日一题-前缀树(Trie)

时间:2021-07-31 13:17:51

【python】Leetcode每日一题-前缀树(Trie)

【题目描述】

Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

请你实现 Trie 类:

Trie() 初始化前缀树对象。

void insert(String word) 向前缀树中插入字符串 word

boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回false

boolean startsWith(String prefix) 如果之前已经插入的字符串word的前缀之一为 prefix ,返回 true ;否则,返回 false

示例1:

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true] 解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True

提示:

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次

【分析】

  • 前缀树(Trie)️重要

    一图解千愁:

    【python】Leetcode每日一题-前缀树(Trie)

  • 代码

class Trie(object):
N = 100009
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie = [[0] * self.N for i in range(26)]
self.count = [0] * self.N
self.index = 0 def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
p = 0
for i in range(len(word)):
u = ord(word[i]) - ord('a')
if self.trie[u][p] == 0:
self.index += 1
self.trie[u][p] = self.index
p = self.trie[u][p]
self.count[p] += 1 def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
p = 0
for i in range(len(word)):
u = ord(word[i]) - ord('a')
if self.trie[u][p] == 0:
return False
p = self.trie[u][p]
return self.count[p] != 0 def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
p = 0
for i in range(len(prefix)):
u = ord(prefix[i]) - ord('a')
if self.trie[u][p] == 0:
return False
p = self.trie[u][p]
return True
  • 另外看到高赞题解,学习到还有一种二维数组法

    有需要的可以直接看原解,不过时间复杂度和空间复杂度都大很多。

【python】Leetcode每日一题-前缀树(Trie)的更多相关文章

  1. 【python】Leetcode每日一题-寻找旋转排序数组中的最小元素

    [python]Leetcode每日一题-寻找旋转排序数组中的最小元素 [题目描述] 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组.例如,原数组nums ...

  2. 【python】Leetcode每日一题-删除有序数组中的重复项

    [python]Leetcode每日一题-删除有序数组中的重复项 [题目描述] 给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现一次 ,返回删除后数组的新长度. 不要 ...

  3. 【python】Leetcode每日一题-存在重复元素3

    [python]Leetcode每日一题-存在重复元素3 [题目描述] 给你一个整数数组 nums 和两个整数 k 和 t .请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] ...

  4. 【python】Leetcode每日一题-扰乱字符串

    [python]Leetcode每日一题-扰乱字符串 [题目描述] 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 > 1 ,执行 ...

  5. 【python】Leetcode每日一题-打家劫舍2

    [python]Leetcode每日一题-打家劫舍2 [题目描述] 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金.这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋 ...

  6. 【python】Leetcode每日一题-二叉搜索树节点最小距离

    [python]Leetcode每日一题-二叉搜索树节点最小距离 [题目描述] 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 . 示例1: 输入:root = [4 ...

  7. 【python】Leetcode每日一题-最大数

    [python]Leetcode每日一题-最大数 [题目描述] 给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数. 注意:输出结果可能非常大,所以你需要返回一个 ...

  8. 【python】Leetcode每日一题-丑数2

    [python]Leetcode每日一题-丑数2 [题目描述] 给你一个整数 n ,请你找出并返回第 n 个 丑数 . 丑数 就是只包含质因数 2.3 和/或 5 的正整数. 示例1: 输入:n = ...

  9. 【python】Leetcode每日一题-丑数

    [python]Leetcode每日一题-丑数 [题目描述] 给你一个整数 n ,请你判断 n 是否为 丑数 .如果是,返回 true :否则,返回 false . 丑数 就是只包含质因数 2.3 和 ...

随机推荐

  1. 高性能Javascript--高效的数据访问

    接上一篇,希望能写一个高性能Javascript专题. 第一篇:高性能Javascript--脚本的无阻塞加载策略. 参考摘录<高性能Javascript>. 经典计算机科学的一个问题是, ...

  2. &lbrack;转&rsqb;VS2012 快捷键

    Ctrl+E,D ----格式化全部代码       Ctrl+A+K+F Ctrl+E,F ----格式化选中的代码     Ctrl+K+F CTRL + SHIFT + B生成解决方案   Al ...

  3. windows平台快速安装 matplotlib

    版本:Python2.7.9 Pip 1.5.6 如果没有安装VC2008以上版本,就需要工具Microsoft Visual C++ Compiler for Python 2.7 http://w ...

  4. xcode解决问题dyld&colon; Library not loaded

    一.问题 编译通过,联机调试时,应用启动闪退,XCODE的Output出现提示: dyld: Library not loaded: /System/Library/Frameworks/AdSupp ...

  5. HTML5 开发APP&lpar; 支付宝支付&rpar;

    我们搞app有一个重要的功能那就是支付功能.无论是微信支付,支付宝,还是银联支付总要有一样支付手段来支持我们网上付款.实现完整的功能.我们公司app的支付方式经过大家开会讨论选择了支付宝支付(其实是当 ...

  6. cap deploy&colon;setup报错

    今天部署cap的时候,setup出现以下错误: 查询半天未果,不过最后还是在google找到了,可见度娘极为不靠谱! I had the same error on deploy:setup with ...

  7. Unity UGUI基础之Button

    UGUI Button,可以说是真正的使用最广泛.功能最全面.几乎涵盖任何模块无所不用无所不能的组件,掌握了它的灵巧使用,你就几乎掌握了大半个UGUI! 一.Button组件: Interactabl ...

  8. &lbrack;dev&rsqb; Go的协程切换问题

    子标题:runtime.Gosched() 是干嘛用的? 1. go程序都有一个环境变量,做线程数设置 GOMAXPROCS 2. 当协程数小于等于线程数的时候,程序行为上与多线程没有区别. 3. 当 ...

  9. jmeter多sql查询

    背景:实现多条sql语句,取多个值的情况 步骤:1.JDBC Connection Configuration配置添加?allowMultiQueries=true 2.增加sql语句 ,查询或修改语 ...

  10. Java —— 对象

    创建对象 int[] b = new int[30]; 等号右侧:创建了一个数组对象  // 等号左侧:变量 b 称为该对应的引用  // 称作 变量 b 指向了一个对象  // 有时也简称为: b ...