676. 实现一个魔法字典

Difficulty
Medium
Tags
前缀树
URL
https://leetcode-cn.com/problems/implement-magic-dictionary/
Star
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 MagicDictionary 类：
  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
示例：
输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["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 <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

前缀树

思路
建立一颗前缀树，在前缀树上做DFS
题解
class TrieNode:
    def __init__(self):
        self.child = {}
        self.word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.child:
                node.child[char] = TrieNode()
            node = node.child[char]
        
        node.word = word


class MagicDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.T = Trie()      

    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            self.T.insert(word)

    def search(self, searchWord: str) -> bool:
        return self.dfs(searchWord, 0, self.T.root, 0)

    def dfs(self, searchWord, start, node, time):
        """以 node 为起点搜索字符串 searchWord[start:] time 为修改次数 
        params:
            start: 当前搜索的字符
            time: 修改的次数
        """
        if start >= len(searchWord) and time == 1 and node.word is not None:
            return True

        if start >= len(searchWord) or time >= 2:
            return False
        
        # 遍历该节点的所有子节点
        for cur_char, next_node in node.child.items():
            # 存在当前字符， time不需要加1
            if cur_char == searchWord[start]:
                if self.dfs(searchWord, start+1,next_node, time):
                    return True
            # 当前字符修改了，time + 1
            else:
                if self.dfs(searchWord, start+1,next_node, time + 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)