热度网络网站建设,台前网站建设公司,网站建设:宏智网络科技,中山免费企业网站建设Python算法题集_实现 Trie [前缀树] 题208#xff1a;实现 Trie (前缀树)1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【定义数据类默认字典】2) 改进版一【初始化字典无额外类】3) 改进版二【字典保存结尾信息无额外类】 4. 最优算法5. 相关… Python算法题集_实现 Trie [前缀树] 题208实现 Trie (前缀树)1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【定义数据类默认字典】2) 改进版一【初始化字典无额外类】3) 改进版二【字典保存结尾信息无额外类】 4. 最优算法5. 相关资源 本文为Python算法题集之一的代码示例
题208实现 Trie (前缀树)
1. 示例说明 Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补完和拼写检查。 请你实现 Trie 类 Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。 示例 输入
[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 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次 2. 题目解析
- 题意分解
本题是为自动补完、拼写检查等创造一个高效率的检索类基本的设计思路迭代单词每层用字典保存同时还需要保存单词结尾信息【search检测结尾、startWith不检测】
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 可以尝试使用默认字典defaultdict 本题都是小写字母因此26个元素的字典就可以保存一个层级 所有单词字符都是ASCII码Ord值都在0-127因此128个元素的字典可以正常使用【超时测试用例需要128一层】 可以考虑将单词结尾信息保存在字典中用一个单词中不会出现的字符即可比如’#’ - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】因此需要本地化测试解决数据波动问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题本地化超时测试用例自己生成详见章节【最优算法】需要安装和部署**NLTK** 3. 代码展开
1) 标准求解【定义数据类默认字典】
使用默认字典定位专门的数据类使用类属性保存单词结尾信息
页面功能测试马马虎虎超过33%
import CheckFuncPerf as cfpclass prenode:def __init__(self):self.chars defaultdict(int)class Trie_base:def __init__(self):self.node prenode()self.bEnd Falsedef searchPrefix(self, prefix):tmpNode selffor achar in prefix:ichar ord(achar) - ord(a)if tmpNode.node.chars[ichar] 0:return NonetmpNode tmpNode.node.chars[ichar]return tmpNodedef insert(self, word):tmpNode selffor achar in word:ichar ord(achar) - ord(a)if tmpNode.node.chars[ichar] 0:tmpNode.node.chars[ichar] Trie_base()tmpNode tmpNode.node.chars[ichar]tmpNode.bEnd Truedef search(self, word):node self.searchPrefix(word)return node is not None and node.bEnddef startsWith(self, prefix):return self.searchPrefix(prefix) is not NonetmpTrie Trie_base()
result cfp.getTimeMemoryStr(testTrie, tmpTrie, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 testTrie 的运行时间为 7127.62 ms内存使用量为 373008.00 KB 执行结果 992) 改进版一【初始化字典无额外类】
将字典数据和单词结尾信息都保存在节点类中创建类同时初始化字典的128个元素【按题意只需26本类已经按超时测试改写】
页面功能测试马马虎虎超过65%
import CheckFuncPerf as cfpclass Trie_ext1:def __init__(self):self.data [None] * 128self.bEnd Falsedef searchPrefix(self, prefix):tmpnode selffor achar in prefix:ichar ord(achar)if not tmpnode.data[ichar]:return Nonetmpnode tmpnode.data[ichar]return tmpnodedef insert(self, word):tmpnode selffor achar in word:ichar ord(achar)if not tmpnode.data[ichar]:tmpnode.data[ichar] Trie_ext1()tmpnode tmpnode.data[ichar]tmpnode.bEnd Truedef search(self, word):tmpnode self.searchPrefix(word)return tmpnode is not None and tmpnode.bEnddef startsWith(self, prefix):return self.searchPrefix(prefix) is not NonetmpTrie Trie_ext1()
result cfp.getTimeMemoryStr(testTrie, tmpTrie, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 testTrie 的运行时间为 5857.32 ms内存使用量为 793700.00 KB 执行结果 993) 改进版二【字典保存结尾信息无额外类】
在字典中保存单词结尾信息将字典数据保存在节点类中创建类时不初始化字典
页面功能测试性能卓越超越96%
import CheckFuncPerf as cfpclass Trie_ext2:def __init__(self):self.tree {}def insert(self, word):tree self.treefor achar in word:if achar not in tree:tree[achar] {}tree tree[achar]tree[#] #def search(self, word):tree self.treefor achar in word:if achar not in tree:return Falsetree tree[achar]return # in treedef startsWith(self, prefix):tree self.treefor achar in prefix:if achar not in tree:return Falsetree tree[achar]return TruetmpTrie Trie_ext2()
result cfp.getTimeMemoryStr(testTrie, tmpTrie, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 testTrie 的运行时间为 1670.38 ms内存使用量为 146692.00 KB 执行结果 994. 最优算法
根据本地日志分析最优算法为第3种方式【字典保存结尾信息无额外类】Trie_ext2
本题大概有以下结论
独立的变量如果能保存在字典结构里减少独立的变量数可以提升性能数据集的默认初始化可能会扩大内存使用同时数据量过大、内存过大也拖累性能
import random
from nltk.corpus import words
word_list list(words.words())
def testTrie(aTrie, actions):for act in actions:if act[0]1: # insertaTrie.insert(act[1])elif act[0]2: # searchaTrie.search(act[1])elif act[0]3: # startsWithaTrie.startsWith(act[1])return 99
import random
actions []
iLen 1000000
for iIdx in range(iLen):actions.append([random.randint(1, 3), random.choice(word_list)])
tmpTrie Trie_base()
result cfp.getTimeMemoryStr(testTrie, tmpTrie, actions)
print(result[msg], 执行结果 {}.format(result[result]))
tmpTrie Trie_ext1()
result cfp.getTimeMemoryStr(testTrie, tmpTrie, actions)
print(result[msg], 执行结果 {}.format(result[result]))
tmpTrie Trie_ext2()
result cfp.getTimeMemoryStr(testTrie, tmpTrie, actions)
print(result[msg], 执行结果 {}.format(result[result]))# 算法本地速度实测比较
函数 testTrie 的运行时间为 7127.62 ms内存使用量为 373008.00 KB 执行结果 99
函数 testTrie 的运行时间为 5857.32 ms内存使用量为 793700.00 KB 执行结果 99
函数 testTrie 的运行时间为 1670.38 ms内存使用量为 146692.00 KB 执行结果 995. 相关资源
本文代码已上传到CSDN地址**Python算法题源代码_LeetCode(力扣)_**实现Trie(前缀树)
一日练一日功一日不练十日空
may the odds be ever in your favor ~
