当前位置:网站首页>leetcode:648. 单词替换【字典树板子 + 寻找若干前缀中的最短符合前缀】
leetcode:648. 单词替换【字典树板子 + 寻找若干前缀中的最短符合前缀】
2022-07-07 12:35:00 【白速龙王的回眸】
分析
来个Trie记录字典树
然后一个个单词遍历,用cur去到当前层
如果遍历到某个c,没有在cur中,设置cur[c]为空, cur = cur[c]
结尾的时候来个#表示结束符
然后遍历sentence中的每个单词,如果遍历到#说明匹配到某个前缀了,进行前缀替换
如果发现当前c不在cur中,说明匹配不下去了,直接break
ac code
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
# 字典树板子
trie = {
}
for word in dictionary:
cur = trie
for c in word:
# 新增分支
if c not in cur:
cur[c] = {
}
cur = cur[c]
# 结束标志
cur['#'] = {
}
words = sentence.split()
for i in range(len(words)):
# 在trie寻找最短前缀
cur = trie
for j, c in enumerate(words[i]):
# 匹配到第一个前缀
if '#' in cur:
words[i] = words[i][:j]
break
# 匹配失败
if c not in cur:
break
# 继续匹配
cur = cur[c]
#print(words)
return ' '.join(words)
总结
字典树板子
可以寻找若干前缀中的最短符合前缀
边栏推荐
- Cesium 已知一点经纬度和距离求另一个点的经纬度
- 一文读懂数仓中的pg_stat
- Excusez - moi, l'exécution a été réussie lors de l'utilisation des données de puits SQL Flink à Kafka, mais il n'y a pas de nombre dans Kafka
- Leetcode——236. 二叉树的最近公共祖先
- OAuth 2.0 + JWT 保护API安全
- The longest ascending subsequence model acwing 1014 Mountaineering
- Vmware共享主机的有线网络IP地址
- Use case diagram
- 手里的闲钱是炒股票还是买理财产品好?
- Million data document access of course design
猜你喜欢
随机推荐
Parameter keywords final, flags, internal, mapping keywords internal
内部排序——插入排序
Parsing of XML files
Csma/cd carrier monitoring multipoint access / collision detection protocol
OAuth 2.0 + JWT 保护API安全
【网络安全】sql注入语法汇总
Excusez - moi, l'exécution a été réussie lors de l'utilisation des données de puits SQL Flink à Kafka, mais il n'y a pas de nombre dans Kafka
课设之百万数据文档存取
c#通过frame 和 page 切换页面
Million data document access of course design
FC连接数据库,一定要使用自定义域名才能在外面访问吗?
gvim【三】【_vimrc配置】
Introduction to sakt method
wpf dataGrid 实现单行某个数据变化 ui 界面随之响应
PERT图(工程网络图)
NLLB-200:Meta开源新模型,可互译200种语言
CSMA/CD 载波监听多点接入/碰撞检测协议
Transferring files between VMware and host
Bashrc and profile
How to check the ram and ROM usage of MCU through Keil