当前位置:网站首页>leetcode:648. Word replacement [dictionary tree board + find the shortest matching prefix among several prefixes]
leetcode:648. Word replacement [dictionary tree board + find the shortest matching prefix among several prefixes]
2022-07-07 14:39:00 【White speed Dragon King's review】
analysis
To a Trie Record dictionary tree
Then traverse word by word , use cur Go to the current layer
If you traverse to a c, Not in the cur in , Set up cur[c] It's empty , cur = cur[c]
At the end, let's say # It means the ending
Then traverse sentence Every word in , If you traverse to # Description matches a prefix , Prefix replacement
If you find out that c be not in cur in , It means that there is no match , direct break
ac code
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
# Dictionary tree board
trie = {
}
for word in dictionary:
cur = trie
for c in word:
# New branch
if c not in cur:
cur[c] = {
}
cur = cur[c]
# End mark
cur['#'] = {
}
words = sentence.split()
for i in range(len(words)):
# stay trie Find the shortest prefix
cur = trie
for j, c in enumerate(words[i]):
# Match to the first prefix
if '#' in cur:
words[i] = words[i][:j]
break
# Matching failure
if c not in cur:
break
# Continue matching
cur = cur[c]
#print(words)
return ' '.join(words)
summary
Dictionary tree board
You can find the shortest matching prefix among several prefixes
边栏推荐
- Leetcode——236. 二叉树的最近公共祖先
- 电脑Win7系统桌面图标太大怎么调小
- Assign a dynamic value to the background color of DataGrid through ivalueconverter
- Wechat applet - Advanced chapter component packaging - Implementation of icon component (I)
- The method of parsing PHP to jump out of the loop and the difference between continue, break and exit
- Nllb-200: meta open source new model, which can translate 200 languages
- 多商戶商城系統功能拆解01講-產品架構
- Mmkv use and principle
- Excuse me, does PTS have a good plan for database pressure measurement?
- Search engine interface
猜你喜欢
云上“视界” 创新无限 | 2022阿里云直播峰会正式上线
Navigation - are you sure you want to take a look at such an easy-to-use navigation framework?
Mrs offline data analysis: process OBS data through Flink job
PyTorch模型训练实战技巧,突破速度瓶颈
2022pagc Golden Sail award | rongyun won the "outstanding product technology service provider of the year"
多商戶商城系統功能拆解01講-產品架構
拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条...
Huawei cloud database DDS products are deeply enabled
LeetCode 648. Word replacement
Cvpr2022 | backdoor attack based on frequency injection in medical image analysis
随机推荐
2022PAGC 金帆奖 | 融云荣膺「年度杰出产品技术服务商」
Simple use of websocket
Instructions for mictr01 tester vibrating string acquisition module development kit
Because the employee set the password to "123456", amd stolen 450gb data?
oracle 触发器实现级联更新
什么是云原生?这回终于能搞明白了!
Computer win7 system desktop icon is too large, how to turn it down
Ascend 910实现Tensorflow1.15实现LeNet网络的minist手写数字识别
electron remote 报错
NLLB-200:Meta开源新模型,可互译200种语言
The longest ascending subsequence model acwing 1012 Sister cities
属性关键字OnDelete,Private,ReadOnly,Required
The method of parsing PHP to jump out of the loop and the difference between continue, break and exit
多商戶商城系統功能拆解01講-產品架構
LeetCode每日一题(636. Exclusive Time of Functions)
Leetcode one question per day (636. exclusive time of functions)
JS in the browser Base64, URL, blob mutual conversion
LeetCode 648. 单词替换
回归测试的分类
Search engine interface