# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + active=""
# 说明：
#     设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 
#     如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
#     实现 MagicDictionary 类：
#         1、MagicDictionary() 初始化对象
#         2、void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
#         3、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

# +
class Node:
    def __init__(self):
        self.children = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = Node()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = Node()
            node = node.children[c]
        node.isWord = True

class MagicDictionary:

    def __init__(self):
        self.trie = Trie()

    def buildDict(self, dictionary) -> None:
        for word in dictionary:
            self.trie.insert(word)
    
    def check(self, node, word):
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.isWord
            
    def search(self, searchWord: str) -> bool:
        node = self.trie.root
        for i, c in enumerate(searchWord):
            if c not in node.children:
                for key in node.children:
                    if self.check(node.children[key], searchWord[i+1:]):
                        return True
                return False
            elif len(node.children) > 1:
                chars = list(node.children.keys())
                for char in chars:
                    if char != c and self.check(node.children[char], searchWord[i+1:]):
                        return True
            node = node.children[c]
        return False


# -

obj = MagicDictionary()
obj.buildDict(["hello","leetcode"])
param_2 = obj.search(searchWord='hello')
print(param_2)



["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello","hallo","leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]



def check(self, node, word):
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.isWord
            
    def search(self, searchWord: str) -> bool:
        node = self.trie.root
        count = 0
        for i, c in enumerate(searchWord):
            if c not in node.children:
                for key in node.children:
                    if self.check(node.children[key], searchWord[i+1:]):
                        return True
                return False
            if len(node.children) > 1:
                count += 1
            node = node.children[c]
        return count == 1 and node.isWord

StarcoderdataJupyterScriptsDedupFiltered