【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)️重要
一图解千愁:
代码
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)的更多相关文章
-
【python】Leetcode每日一题-寻找旋转排序数组中的最小元素
[python]Leetcode每日一题-寻找旋转排序数组中的最小元素 [题目描述] 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组.例如,原数组nums ...
-
【python】Leetcode每日一题-删除有序数组中的重复项
[python]Leetcode每日一题-删除有序数组中的重复项 [题目描述] 给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现一次 ,返回删除后数组的新长度. 不要 ...
-
【python】Leetcode每日一题-存在重复元素3
[python]Leetcode每日一题-存在重复元素3 [题目描述] 给你一个整数数组 nums 和两个整数 k 和 t .请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] ...
-
【python】Leetcode每日一题-扰乱字符串
[python]Leetcode每日一题-扰乱字符串 [题目描述] 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 > 1 ,执行 ...
-
【python】Leetcode每日一题-打家劫舍2
[python]Leetcode每日一题-打家劫舍2 [题目描述] 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金.这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋 ...
-
【python】Leetcode每日一题-二叉搜索树节点最小距离
[python]Leetcode每日一题-二叉搜索树节点最小距离 [题目描述] 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 . 示例1: 输入:root = [4 ...
-
【python】Leetcode每日一题-最大数
[python]Leetcode每日一题-最大数 [题目描述] 给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数. 注意:输出结果可能非常大,所以你需要返回一个 ...
-
【python】Leetcode每日一题-丑数2
[python]Leetcode每日一题-丑数2 [题目描述] 给你一个整数 n ,请你找出并返回第 n 个 丑数 . 丑数 就是只包含质因数 2.3 和/或 5 的正整数. 示例1: 输入:n = ...
-
【python】Leetcode每日一题-丑数
[python]Leetcode每日一题-丑数 [题目描述] 给你一个整数 n ,请你判断 n 是否为 丑数 .如果是,返回 true :否则,返回 false . 丑数 就是只包含质因数 2.3 和 ...
随机推荐
-
高性能Javascript--高效的数据访问
接上一篇,希望能写一个高性能Javascript专题. 第一篇:高性能Javascript--脚本的无阻塞加载策略. 参考摘录<高性能Javascript>. 经典计算机科学的一个问题是, ...
-
[转]VS2012 快捷键
Ctrl+E,D ----格式化全部代码 Ctrl+A+K+F Ctrl+E,F ----格式化选中的代码 Ctrl+K+F CTRL + SHIFT + B生成解决方案 Al ...
-
windows平台快速安装 matplotlib
版本:Python2.7.9 Pip 1.5.6 如果没有安装VC2008以上版本,就需要工具Microsoft Visual C++ Compiler for Python 2.7 http://w ...
-
xcode解决问题dyld: Library not loaded
一.问题 编译通过,联机调试时,应用启动闪退,XCODE的Output出现提示: dyld: Library not loaded: /System/Library/Frameworks/AdSupp ...
-
HTML5 开发APP( 支付宝支付)
我们搞app有一个重要的功能那就是支付功能.无论是微信支付,支付宝,还是银联支付总要有一样支付手段来支持我们网上付款.实现完整的功能.我们公司app的支付方式经过大家开会讨论选择了支付宝支付(其实是当 ...
-
cap deploy:setup报错
今天部署cap的时候,setup出现以下错误: 查询半天未果,不过最后还是在google找到了,可见度娘极为不靠谱! I had the same error on deploy:setup with ...
-
Unity UGUI基础之Button
UGUI Button,可以说是真正的使用最广泛.功能最全面.几乎涵盖任何模块无所不用无所不能的组件,掌握了它的灵巧使用,你就几乎掌握了大半个UGUI! 一.Button组件: Interactabl ...
-
[dev] Go的协程切换问题
子标题:runtime.Gosched() 是干嘛用的? 1. go程序都有一个环境变量,做线程数设置 GOMAXPROCS 2. 当协程数小于等于线程数的时候,程序行为上与多线程没有区别. 3. 当 ...
-
jmeter多sql查询
背景:实现多条sql语句,取多个值的情况 步骤:1.JDBC Connection Configuration配置添加?allowMultiQueries=true 2.增加sql语句 ,查询或修改语 ...
-
Java —— 对象
创建对象 int[] b = new int[30]; 等号右侧:创建了一个数组对象 // 等号左侧:变量 b 称为该对应的引用 // 称作 变量 b 指向了一个对象 // 有时也简称为: b ...