676 实现一个魔法字典（Trie树、dfs）

野性酷女 2022-09-02 13:55 152阅读 0赞

**1. 问题描述：**

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。  
实现 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  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/implement-magic-dictionary

**2. 思路分析：**

分析题目可以知道我们需要设计一个数据结构来存储所有的单词，并且这个数据结构能够支持查询操作，在查询单词的过程中能够判断出是否存在一个单词与当前查询的单词只存在一个字符是不同的。因为查询的时候我们需要判断出这个数据结构中是否只存在一个字符是不同的，所以我们想到**Trie树**来存储这些单词，并且Trie树能够支持查询所有单词的操作。Trie树在存储的这些单词的时候相当于是创建了一棵多叉树，每一个单词存在自己独立的分支，而且在查询单词的时候我们可以搜索整棵Trie树，这样就可以比较当前搜索的单词的字符与查询单词的字符是否相同。所以对于buildDict方法我们可以将所有的单词插入到Trie树中，对于search方法我们通过搜索Trie树中的所有单词（dfs），判断是否存在一个单词与当前单词只有一个字符，如果在搜索的过程中发现找到了符合的单词之后直接返回True。下面是使用字典来链接字符与字符之间关系创建的Trie树， 单词列表为\["a", "b", "ab", "abc"\]：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

from typing import List
    
    
    class MagicDictionary:
        dic = None
    
        # Trie树的初始化
        def __init__(self):
            self.dic = dict()
    
        # 往Trie树中插入单词
        def insert(self, w: str):
            t = self.dic
            for c in w:
                if c not in t:
                    t[c] = {}
                t = t[c]
            # 当前的单词结束标志
            t["end"] = 1
    
        # 调用Trie树的插入单词的函数往Trie树中插入所有的单词
        def buildDict(self, dictionary: List[str]) -> None:
            for w in dictionary:
                self.insert(w)
    
        # c表示当前Trie树中搜索的单词与查询单词的不同的字符数目, u表示当前searchWord的位置, t表示当前Trie树位于哪个层, t是一个字典
        def dfs(self, searchWord: str, c: int, u: int, t: dict):
            # 搜索到了Trie树中当前单词和searchword单词的末尾并且不同字符的个数为1
            if u == len(searchWord) and c == 1 and "end" in t: return True
            if c > 1 or u == len(searchWord): return False
            for k, v in t.items():
                # 因为当前的可能是某个单词的结束标记, 所以当前键是end的时候continue, 但是不能够直接返回False因为可能存在其他合法的分支
                if k == "end": continue
                if self.dfs(searchWord, c + 1 if k != searchWord[u] else c, u + 1, t[k]):  return True
            return False
    
        def search(self, searchWord: str) -> bool:
            t = self.dic
            return self.dfs(searchWord, 0, 0, t)
    
    
    # if __name__ == '__main__':
    #     obj = MagicDictionary()
    #     obj.buildDict(["a", "b", "ab", "abc"])
    #     res = obj.search("hello")
    #     print(res)
    #     res = obj.search("hhllo")
    #     print(res)
    #     res = obj.search("abb")
    #     print(res)

**使用idx唯一标识每一个节点：**

from typing import List
    class MagicDictionary:
        def __init__(self):
             # N为节点的个数, 因为单词的长度最大为100而且插入单词最多是100次, 所以节点个数最多为10000
             N = 10050
             # son表示Trie树, 第一维标识字符串前缀, 第二维标识当前前缀的最后一个字符
             son = [[0] * 26 for i in range(N)]
             self.son = son
             # idx用来标识每一个单词
             self.idx = 1
             # is_end用来记录单词的结尾标志
             is_end = [0] * N
             self.is_end = is_end
             
        def insert(self, w: str):
             son = self.son
             p = 0
             for c in w:
                  k = ord(c) - ord("a")
                  if son[p][k] == 0:
                       son[p][k] = self.idx
                       self.idx += 1
                  p = son[p][k]
             self.is_end[p] = p
              
     
        def buildDict(self, dictionary: List[str]) -> None:
              for w in dictionary:
                   self.insert(w)
        # k为当前递归的位置, count用来记录当前与prefix不同字符的个数, p表示Trie树节点的位置
        def dfs(self, prefix: str, k: int, count: int, p: int):
              if k == len(prefix) and count == 1 and self.is_end[p]: return True
              if count > 1 or k == len(prefix): return False
              for c in range(26):
                   # 只有当当前位置大于0说明Trie树中存在当前的节点
                   if self.son[p][c] > 0:
                        # 所有单词的字符都是小写字母, 当找到对应的满足要求的单词之后直接返回True
                        if self.dfs(prefix, k + 1, count + 1 if chr(c + 97) != prefix[k] else count, self.son[p][c]):  return True
              return False
                        
             
        def search(self, searchWord: str) -> bool:
              # dfs搜索Trie树中的所有单词
              return self.dfs(searchWord, 0, 0, 0)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/011d5b9131294348bf1435d0faa7ab85.png