# 0676. Implement Magic Dictionary
###### tags: `Leetcode` `Medium` `FaceBook` `Trie`
Link: https://leetcode.com/problems/implement-magic-dictionary/
## 思路
用Trie
对于每个位置的字符，都尝试修改一遍，然后用find函数找修改的字符后面的子字串是否包含在trie里面，如果包含则返回true
时间复杂度：假设字符串的平均长度是k，那么构建trie的时间复杂度是$O(nk)$ 搜寻trie最差的time complexity是$O(26k^2)$，因为最差就是只有最后一个字母不一样
## Code

class MagicDictionary {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
        public TrieNode(){}
    }
    TrieNode root;
    public MagicDictionary() {
        root = new TrieNode();
    }
    
    public void buildDict(String[] dictionary) {
        for(String s:dictionary){
            TrieNode curr = root;
            for(int i = 0;i < s.length();i++){
                if(curr.children[s.charAt(i)-'a'] == null){
                    curr.children[s.charAt(i)-'a'] = new TrieNode();
                }
                curr = curr.children[s.charAt(i)-'a'];
            }
            curr.isWord = true;
        }
    }
    
    public boolean search(String searchWord) {
        char[] arr = searchWord.toCharArray();
        TrieNode curr = root;
        for(int i = 0;i < searchWord.length();i++){
            for(char c = 'a';c <= 'z';c++){
                if(arr[i]==c || curr.children[c-'a']==null) continue;
                if(find(curr.children[c-'a'], searchWord, i+1)) return true;
            }
            if(curr.children[searchWord.charAt(i)-'a']==null) return false;
            curr = curr.children[searchWord.charAt(i)-'a'];
        }
        return false;
    }
    
    public boolean find(TrieNode temp, String s, int idx){
        TrieNode curr = temp;
        for(int i = idx;i < s.length();i++){
            if(curr.children[s.charAt(i)-'a']==null) return false;
            curr = curr.children[s.charAt(i)-'a'];
        }
        return curr.isWord;
    }
}

class TrieNode:
        def __init__(self, char):
            self.char = char
            self.children = {}
            self.is_end = False
    
class MagicDictionary:

    def __init__(self):
        self.trie = TrieNode('#')

    def addWord(self, word):
        root = self.trie
        for char in word:
            if char not in root.children:
                root.children[char] = TrieNode(char)
            
            root = root.children[char]
        root.is_end = True

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

    def dfs(self, modification, searchWord, node):
        if not searchWord:
            return not modification and node.is_end

        for child in node.children.keys():
            if child == searchWord[0]:
                if self.dfs(modification, searchWord[1:], node.children[child]):
                    return True
            elif modification > 0:
                if self.dfs(modification-1, searchWord[1:], node.children[child]):
                    return True
        return False
                
    def search(self, searchWord: str) -> bool:
        return self.dfs(1, searchWord, self.trie)