0676. Implement Magic Dictionary¶
题目信息¶
- 题号:
0676
- 难度:
Medium
- 主题:
设计、字典、等长字符串、恰好一次字符替换
- 原题:
- 重点:
search 必须通过替换恰好一个字符匹配字典词、不能零次替换、不能插入或删除字符、对象保留已构建字典
题目重述¶
实现 MagicDictionary。buildDict(dictionary) 使用给定字符串数组建立字典;search(searchWord) 判断能否把 searchWord 中恰好一个位置的字符替换成另一个小写字母,使修改后的字符串与字典中的某个单词完全相同。
替换不会改变字符串长度,因此只有等长字典词可能匹配。原字符串直接存在于字典中并不足以返回 true,除非还存在另一个与它恰好相差一个字符的字典词。字典长度位于 [1, 100],单词长度位于 [1, 100],方法总调用次数不超过 100。
自建示例¶
恰好一个字符不同:
调用:buildDict(["hello","judge"]), search("hallo"), search("hello")
输出:true, false
解释:hallo 把第二个字符改为 e 后得到 hello;hello 自身虽然在字典中,但零次替换不符合要求。
长度不同不能通过替换匹配:
调用:buildDict(["code"]), search("codes")
输出:false
解释:替换操作不能删除多出的字符,因此长度 5 的查询词无法匹配长度 4 的字典词。