剑指 Offer II 064. 神奇的字典
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。
实现 MagicDictionary 类：
MagicDictionary() 初始化对象void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
示例：
输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]
解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
提示：
1 <= dictionary.length <= 1001 <= dictionary[i].length <= 100dictionary[i] 仅由小写英文字母组成dictionary 中的所有字符串 互不相同1 <= searchWord.length <= 100searchWord 仅由小写英文字母组成buildDict 仅在 search 之前调用一次100 次 search
注意：本题与主站 676 题相同： https://leetcode.cn/problems/implement-magic-dictionary/
原站题解
python3 解法, 执行用时: 244 ms, 内存消耗: 19.8 MB, 提交时间: 2022-11-22 09:54:43
class Trie:
def __init__(self):
self.is_finished = False
self.child = dict()
class MagicDictionary:
def __init__(self):
self.root = Trie()
def buildDict(self, dictionary: List[str]) -> None:
for word in dictionary:
cur = self.root
for ch in word:
if ch not in cur.child:
cur.child[ch] = Trie()
cur = cur.child[ch]
cur.is_finished = True
def search(self, searchWord: str) -> bool:
def dfs(node: Trie, pos: int, modified: bool) -> bool:
if pos == len(searchWord):
return modified and node.is_finished
ch = searchWord[pos]
if ch in node.child:
if dfs(node.child[ch], pos + 1, modified):
return True
if not modified:
for cnext in node.child:
if ch != cnext:
if dfs(node.child[cnext], pos + 1, True):
return True
return False
return dfs(self.root, 0, False)
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)
golang 解法, 执行用时: 32 ms, 内存消耗: 8 MB, 提交时间: 2022-11-22 09:50:53
// 字典树
type trie struct {
children [26]*trie
isFinished bool
}
type MagicDictionary struct {
*trie
}
func Constructor() MagicDictionary {
return MagicDictionary{&trie{}}
}
func (d *MagicDictionary) BuildDict(dictionary []string) {
for _, word := range dictionary {
cur := d.trie
for _, c := range word {
c -= 'a'
if cur.children[c] == nil {
cur.children[c] = &trie{}
}
cur = cur.children[c]
}
cur.isFinished = true
}
}
func dfs(node *trie, searchWord string, modified bool) bool {
if searchWord == "" {
return modified && node.isFinished
}
c := searchWord[0] - 'a'
if node.children[c] != nil && dfs(node.children[c], searchWord[1:], modified) {
return true
}
if !modified {
for i, child := range node.children {
if i != int(c) && child != nil && dfs(child, searchWord[1:], true) {
return true
}
}
}
return false
}
func (d *MagicDictionary) Search(searchWord string) bool {
return dfs(d.trie, searchWord, false)
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* obj := Constructor();
* obj.BuildDict(dictionary);
* param_2 := obj.Search(searchWord);
*/
golang 解法, 执行用时: 12 ms, 内存消耗: 6.7 MB, 提交时间: 2022-11-22 09:49:59
type MagicDictionary []string
func Constructor() MagicDictionary {
return MagicDictionary{}
}
func (d *MagicDictionary) BuildDict(dictionary []string) {
*d = dictionary
}
func (d *MagicDictionary) Search(searchWord string) bool {
next:
for _, word := range *d {
if len(word) != len(searchWord) {
continue
}
diff := false
for i := range word {
if word[i] != searchWord[i] {
if diff {
continue next
}
diff = true
}
}
if diff {
return true
}
}
return false
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* obj := Constructor();
* obj.BuildDict(dictionary);
* param_2 := obj.Search(searchWord);
*/
python3 解法, 执行用时: 76 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-22 09:47:22
class MagicDictionary:
def __init__(self):
self.words = list()
def buildDict(self, dictionary: List[str]) -> None:
self.words = dictionary
def search(self, searchWord: str) -> bool:
for word in self.words:
if len(word) != len(searchWord):
continue
diff = 0
for chx, chy in zip(word, searchWord):
if chx != chy:
diff += 1
if diff > 1:
break
if diff == 1:
return True
return False
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)