题目描述:
LeetCode 676. Implement Magic Dictionary
Implement a magic directory with buildDict
, and search
methods.
For the method buildDict
, you'll be given a list of non-repetitive words to build a dictionary.
For the method search
, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.
Example 1:
Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False
Note:
- You may assume that all the inputs are consist of lowercase letters
a-z
. - For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
- Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.
题目大意:
实现数据结构“魔法字典”,支持两种操作:
buildDict:输入一组无重复的单词,构建一个字典
search:在字典中寻找目标串,目标串与搜索串恰好有一个字符不同
解题思路:
创建字典dmap<String, Set>
build操作:用下划线'_'替换word的每一个位置的字母,作为Key,被替换的字母作为Value,存入dmap
search操作:用下划线'_'替换word的每一个位置的字母,作为Key,在dmap中查找与被替换字母不同的值
Python代码:
class MagicDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.dmap = collections.defaultdict(set)
def buildDict(self, dict):
"""
Build a dictionary through a list of words
:type dict: List[str]
:rtype: void
"""
for word in dict:
for x in range(len(word)):
key = word[:x] + '_' + word[x+1:]
self.dmap[key].add(word[x])
def search(self, word):
"""
Returns if there is any word in the trie that equals to the given word after modifying exactly one character
:type word: str
:rtype: bool
"""
for x in range(len(word)):
key = word[:x] + '_' + word[x+1:]
values = self.dmap[key]
if not values: continue
if word[x] not in values or len(values) > 1:
return True
return False
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)
本文链接:http://bookshadow.com/weblog/2017/09/10/leetcode-implement-magic-dictionary/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。